网络流模板-最小费用最大流

最小费用最大流：

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];
	}
}
}; // {}}}