HDU 3549 网络最大流（ dinic ）

        链式向前星存图，BFS 构造分层图，DFS 寻找增广路  HUD 3549

#include<bits/stdc++.h>
#define Inf 0x3F3F3F3F
using namespace std;

const int SIZE = (int)(1E5 + 7);
typedef struct {
	int next, to, w;
} Edge;
Edge edge[SIZE << 1];
int head[SIZE << 1], Deep[SIZE], cnt, aimT;
queue<int> que;

void add(int form, int to, int w) {
	edge[cnt].to = to; 
	edge[cnt].w = w;
	edge[cnt].next = head[form];
	head[form] = cnt++;
}

int BFS(int S, int T) {
	memset(Deep, 0, sizeof Deep);
	while (!que.empty()) que.pop();
	Deep[S] = 1; que.push(S);
	while (!que.empty()) {
		int now = que.front(); que.pop();
		for (int pos = head[now]; ~pos; pos = edge[pos].next)
			if (edge[pos].w && !Deep[edge[pos].to]) {
				Deep[edge[pos].to] = Deep[now] + 1;
				que.push(edge[pos].to);
			}
	}
	return Deep[T];
}

int DFS(int now, int rem) {
	if (now == aimT) return rem;
	int all_flow = 0;
	for (int pos = head[now]; ~pos && rem; pos = edge[pos].next) {
		if (edge[pos].w && Deep[edge[pos].to] == Deep[now] + 1) {
			int add_flow = DFS(edge[pos].to, min(rem, edge[pos].w));
			
			edge[pos].w -= add_flow; 
			edge[pos ^ 1].w += add_flow;
			
			rem -= add_flow; all_flow += add_flow;
		}
	}
	
	if (all_flow == 0)
		Deep[now] = -1;
	return all_flow;
}

int Dinic(int S, int T) {
	aimT = T; int ans = 0;
	while (BFS(S, T))
		ans += DFS(S, Inf);
	return ans;
}

int main() {
	int form, to, w, path, total, point;
	scanf("%d", &total);
	
	for(int ind = 1; ind <= total; ind++){
		memset(head, -1, sizeof head), cnt = 0;
		
		scanf("%d%d", &point, &path);
		while (path--) {
			scanf("%d%d%d", &form, &to, &w);
			add(form, to, w); add(to, form, 0);
		}
		printf("Case %d: %d\n", ind, Dinic(1, point));
	}
}