【模板】最小费用流模板

（待更新）
有一种类似于Dinic的写法

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1000;
const int MAXM = 30010;
const int INF = 2147483647;
namespace Dinic {
	struct Edge {
		int from,to,cap,cost,flow;
		Edge() {}
		Edge(int from,int to,int cap,int cost,int flow):
			from(from), to(to), cap(cap), cost(cost), flow(flow) {}
	};
	int n,m,s,t;
	int head[MAXN],nxt[MAXM];
	Edge edge[MAXM];
	int dist[MAXN],cur[MAXN];
	void clear(int _n) {
		n = _n;
		m = 0;
		memset(head,255,sizeof head);
	}
	void addedge(int from,int to,int cap,int cost) {
		edge[m] = Edge(from,to,cap,cost,0);
		nxt[m] = head[from];
		head[from] = m++;
		edge[m] = Edge(to,from,0,-cost,0);
		nxt[m] = head[to];
		head[to] = m++;
	}
	queue<int> q;
	bool inq[MAXN];
	bool spfa() {
		for(int i = 0; i < n; ++i)
			dist[i] = INF;
		memset(inq,0,sizeof inq);
		dist[s] = 0;
		q.push(s);
		inq[s] = 1;
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			inq[u] = 0;
			for(int i = head[u]; ~i; i = nxt[i]) {
				Edge &e = edge[i];
				if(e.cap > e.flow && dist[e.to] > dist[u] + e.cost) {
					dist[e.to] = dist[u] + e.cost;
					if(!inq[e.to]) {
						inq[e.to] = 1;
						q.push(e.to);
					}
				}
			}
		}
		return dist[t] != INF;
	}
	int cost;
	bool vis[MAXN];
	int dfs(int u,int res) {
		vis[u] = 1;
		if(u == t || !res) {return cost += dist[t] * res, res;}
		int flow = 0, f;
		for(int &i = cur[u]; ~i; i = nxt[i]) {
			Edge &e = edge[i];
			if(e.cap > e.flow && dist[e.to] == dist[u] + e.cost && (!vis[e.to])) {
				f = dfs(e.to,min(e.cap - e.flow,res));
				e.flow += f;
				edge[i^1].flow -= f;
				flow += f;
				res -= f;
				if(!res) break;
			}
		}
		return flow;
	}
	int maxflow(int _s,int _t) {
		s = _s;
		t = _t;
		int flow = 0, f;
		while(spfa()) {
			vis[t] = 1;
			while(vis[t]) {
				memset(vis,0,sizeof vis);
				for(int i = 0; i < n; ++i)
					cur[i] = head[i];
				while(f = dfs(s,INF))
					flow += f;
			}
		}
		return flow;
	}
}
int read()
{
	char ch = getchar();
	int x = 0, f = 1;
	while(ch < '0' || ch > '9') {if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
	return x * f;
}
int main() {
	int n,m;
	n = read(), m = read();
	Dinic::clear(n + 1);
	int s,t,c,w;
	for(int i = 1; i <= m; ++i) {
		s = read(), t = read(), c = read(), w = read();
		Dinic::addedge(s,t,c,w);
	}
	printf("%d ",Dinic::maxflow(1,n));
	printf("%d\n",Dinic::cost);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

const int MAXN = 1000;

const int MAXM = 30010;

const int INF = 2147483647;

namespace Dinic {

struct Edge {

int from,to,cap,cost,flow;

Edge() {}

Edge(int from,int to,int cap,int cost,int flow):

from(from), to(to), cap(cap), cost(cost), flow(flow) {}

};

int n,m,s,t;

int head[MAXN],nxt[MAXM];

Edge edge[MAXM];

int dist[MAXN],cur[MAXN];

void clear(int _n) {

n = _n;

m = 0;

memset(head,255,sizeof head);

}

void addedge(int from,int to,int cap,int cost) {

edge[m] = Edge(from,to,cap,cost,0);

nxt[m] = head[from];

head[from] = m++;

edge[m] = Edge(to,from,0,-cost,0);

nxt[m] = head[to];

head[to] = m++;

}

queue<int> q;

bool inq[MAXN];

bool spfa() {

for(int i = 0; i < n; ++i)

dist[i] = INF;

memset(inq,0,sizeof inq);

dist[s] = 0;

q.push(s);

inq[s] = 1;

while(!q.empty()) {

int u = q.front();

q.pop();

inq[u] = 0;

for(int i = head[u]; ~i; i = nxt[i]) {

Edge &e = edge[i];

if(e.cap > e.flow && dist[e.to] > dist[u] + e.cost) {

dist[e.to] = dist[u] + e.cost;

if(!inq[e.to]) {

inq[e.to] = 1;

q.push(e.to);

}

return dist[t] != INF;

}

int cost;

bool vis[MAXN];

int dfs(int u,int res) {

vis[u] = 1;

if(u == t || !res) {return cost += dist[t] * res, res;}

int flow = 0, f;

for(int &i = cur[u]; ~i; i = nxt[i]) {

Edge &e = edge[i];

if(e.cap > e.flow && dist[e.to] == dist[u] + e.cost && (!vis[e.to])) {

f = dfs(e.to,min(e.cap - e.flow,res));

e.flow += f;

edge[i^1].flow -= f;

flow += f;

res -= f;

if(!res) break;

}

return flow;

}

int maxflow(int _s,int _t) {

s = _s;

t = _t;

int flow = 0, f;

while(spfa()) {

vis[t] = 1;

while(vis[t]) {

memset(vis,0,sizeof vis);

for(int i = 0; i < n; ++i)

cur[i] = head[i];

while(f = dfs(s,INF))

flow += f;

}

return flow;

}

int read()

{

char ch = getchar();

int x = 0, f = 1;

while(ch < '0' || ch > '9') {if(ch == '-') f = -f; ch = getchar();}

while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}

return x * f;

}

int main() {

int n,m;

n = read(), m = read();

Dinic::clear(n + 1);

int s,t,c,w;

for(int i = 1; i <= m; ++i) {

s = read(), t = read(), c = read(), w = read();

Dinic::addedge(s,t,c,w);

}

printf("%d ",Dinic::maxflow(1,n));

printf("%d\n",Dinic::cost);

return 0;

}