最小费用最大流：
struct flow { // }{{{
using ll = long long;
constexpr static int V = 5e3, E = 5e4;
constexpr static int EDGE_NIL = -1;
constexpr static ll INF = 0x3f3f3f3f3f3f3f3f;
struct Edge {
int to, nxt, cost, lf;
} edges[E * 2];
struct mypair{
ll dis; int id;
bool operator<(const mypair& a) const{return dis > a.dis;}
mypair(ll d, int x){dis = d, id = x;}
};
ll dis[V], h[V];
int head[V], back[V];
sd bitset<V> vis;
int is, it, iv, cnt;
int maxf, minc;
void init(int v, int s, int t) {
is = s, iv = v, it = t;
cnt = 0;
maxf = minc = 0;
memset(head, 0xff, sizeof head);
}
void addflow(int s, int t, int f, int c) {
edges[cnt] = (Edge) {.to = t, .nxt = head[s], .cost = c, .lf = f}, head[s] = cnt++;
edges[cnt] = (Edge) {.to = s, .nxt = head[t], .cost = -c, .lf = 0}, head[t] = cnt++;
}
bool dijk() {
sd priority_queue<mypair> todo;
memset(dis, 0x3f, sizeof dis);
vis.reset();
dis[is] = 0;
back[is] = EDGE_NIL;
todo.push({0, is});
while (!todo.empty()) {
int s = todo.top().id;
todo.pop();
if(vis[s]) continue;
vis[s] = true;
for (int i = head[s]; i != EDGE_NIL; i = edges[i].nxt) {
int t = edges[i].to;
ll w = (ll)edges[i].cost + h[s] - h[t];
if (edges[i].lf && dis[t] > dis[s] + w) {
dis[t] = dis[s] + w;
back[t] = i ^ 1;
if(!vis[t]) todo.push({dis[t], t});
}
}
}
return dis[it] != INF;
}
void spfa(){
sd queue<int> todo;
vis.reset();
memset(h, 0x3f, sizeof h);
h[is] = 0;
todo.push(is);
while(!todo.empty()){
int s = todo.front();
todo.pop();
vis[s] = false;
for(int i=head[s]; i!=EDGE_NIL; i=edges[i].nxt){
int t = edges[i].to;
if(edges[i].lf && h[t] > h[s] + edges[i].cost){
h[t] = h[s] + edges[i].cost;
if(!vis[t]) vis[t] = 1, todo.push(t);
}
}
}
}
void mcmf() {
spfa();
while (dijk()) {
int df = 0x3f3f3f3f;
UP(i, 0, iv) h[i] += dis[i];
for (int i = back[it]; i != EDGE_NIL; i = back[edges[i].to]) {
df = sd min(df, edges[i ^ 1].lf);
}
for (int i = back[it]; i != EDGE_NIL; i = back[edges[i].to]) {
edges[i].lf += df;
edges[i ^ 1].lf -= df;
}
maxf += df;
minc += df * h[it];
}
}
}; // {}}}