Dinic+弧优化模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 100010;
const int maxm = 1000100;
struct *** {
	int v, w, ne;
}ed[maxm];
int n, m, cnt;
int head[maxn], dis[maxn], cur[maxn];
void init() {
	cnt = 0;
	memset(head, -1, sizeof(head));
}
void add(int u, int v, int w) {
	ed[cnt].v = v; ed[cnt].w = w;
	ed[cnt].ne = head[u]; head[u] = cnt++;
	ed[cnt].v = u, ed[cnt].w = 0;
	ed[cnt].ne = head[v]; head[v] = cnt++;
}
int bfs(int st, int en) {
	queue<int>q;
	memset(dis, 0, sizeof(dis));
	dis[st] = 1;
	q.push(st);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		if (u == en)return 1;
		for (int s = head[u]; ~s; s = ed[s].ne) {
			int v = ed[s].v;
			if (dis[v] == 0 && ed[s].w > 0) {
				dis[v] = dis[u] + 1; q.push(v);
			}
		}
	}
	return dis[en] != 0;
}
int dfs(int st, int en, int flow) {
	int ret = flow, a;
	if (st == en || flow == 0)return flow;
	for (int &s = cur[st]; ~s; s = ed[s].ne) {
		int v = ed[s].v;
		if (dis[v] == dis[st] + 1 && (a = dfs(v, en, min(ret, ed[s].w)))) {
			ed[s].w -= a;
			ed[s ^ 1].w += a;
			ret -= a;
			if (!ret)break;
		}
	}
	if (ret == flow)dis[st] = 0;
	return flow - ret;
}
int dinic(int st, int en) {
	int ans = 0;
	while (bfs(st, en)) {
		for (int s = 1; s <= n; s++) 
			cur[s] = head[s];
		ans += dfs(st, en, inf);
	}
	return ans;
}
int main() {
	int te, cas = 1;
	scanf("%d", &te);
	while (te--) {
		init();
		scanf("%d%d", &n, &m);
		while (m--) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c); 
		}
		int ans = dinic(1, n);
		printf("Case %d: %d\n", cas++, ans);
	}
}