学线性规划的时候发现不能三分钟费用流，而且我之前的模板很丑，于是搞搞，顺便写下没怎么写过的 zkw 费用流。

封装了一下。

最大流

bfs 搜出分层图，dfs 找增广路。

	struct NetworkFlow {
		const int inf = 707406378;
		int S, T;
		int head[N], tot = 1;
		struct Edge {
			int to; ll w; int op, nxt;
		} e[M << 1];
		void add_edge(int u, int v, ll w) {
			e[++tot] = (Edge) {v, w, tot ^ 1, head[u]}, head[u] = tot;
			e[++tot] = (Edge) {u, 0, tot ^ 1, head[v]}, head[v] = tot;
		}
		NetworkFlow() {tot = 1;}

		int dis[N];
		queue <int> q;
		bool bfs() {
			while (!q.empty()) q.pop();
			memset (dis, 127 / 3, sizeof dis);
			dis[S] = 0;
			q.push(S);
			while (!q.empty()) {
				int u = q.front(); q.pop();
				for (int i = head[u]; i; i = e[i].nxt) {
					int v = e[i].to;
					if (dis[v] > dis[u] + 1 && e[i].w) {
						dis[v] = dis[u] + 1;
						if (v == T) return 1;
						q.push(v);
					}
				}
			}
			return 0;
		}
		ll dfs (int u, ll flow) {
			if (u == T) return flow;
			ll sum = 0;
			for (int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to;
				if (dis[v] == dis[u] + 1 && e[i].w) {
					ll f = dfs(v, min(e[i].w, flow - sum));
					if (!f) dis[v] = -1;
					e[i].w -= f;
					e[e[i].op].w += f;
					sum += f;
					if (sum == flow) break;
				}
			}
			return sum;
		}
		ll dinic () { ll ret = 0; for (; bfs(); ret += dfs(S, inf)); return ret; }
	} nf;

费用流

SPFA 倒着搜分层图、最小花费，用到了 SLF 优化，dfs 张昆玮优化。

	struct NetworkFlow {
		const int inf = 707406378;
		int S, T, n;
		int head[N], tot = 1;
		struct Edge {
			int to; ll w, c; int nxt;
		} e[M << 1];
		void add_edge(int u, int v, ll w, ll c) {
			e[++tot] = (Edge) {v, w, c, head[u]}, head[u] = tot;
			e[++tot] = (Edge) {u, 0, -c, head[v]}, head[v] = tot;
		}
		NetworkFlow() {tot = 1;}

		bool vis[N];
		int dis[N];
		deque <int> q;
		bool spfa() {
			while (!q.empty()) q.pop_back();
			for (int i = 1; i <= n; i++) vis[i] = 0, dis[i] = inf;
			dis[T] = 0, vis[T] = 1;
			q.push_back(T);
			while (!q.empty()) {
				int u = q.front(); q.pop_front(); vis[u] = 0;
				for (int i = head[u]; i; i = e[i].nxt) {
					int v = e[i].to;
					if (dis[v] > dis[u] - e[i].c && e[i ^ 1].w) {
						dis[v] = dis[u] - e[i].c;
						if (!vis[v]) {
							vis[v] = 1;
							if (q.size() && dis[v] < dis[q.front()]) q.push_front(v);
							else q.push_back(v);
						}
					}
				}
			}
			return dis[S] < inf;
		}
		ll mcost = 0;
		ll dfs (int u, ll flow) {
			vis[u] = 1;
			if (u == T || !flow) return flow;
			ll sum = 0;
			for (int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to;
				if (dis[v] == dis[u] - e[i].c && e[i].w && !vis[v]) {
					ll f = dfs(v, min(e[i].w, flow - sum));
					if (!f) continue;
					e[i].w -= f;
					e[i ^ 1].w += f;
					sum += f;
					mcost += f * e[i].c;
					if (sum == flow) break;
				}
			}
			return sum;
		}
		ll mcmf () { 
			ll ret = 0; 
			while (spfa()) {
				vis[T] = 1;
				for (; vis[T]; ret += dfs(S, inf))
					for (int i = 1; i <= n; i++) vis[i] = 0;
			} 
			return ret; 
		}
	} nf;