赤裸裸的最大流
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; #define maxn 205 #define maxm 205 #define inf (1 << 30) struct Edge { int next, v, f; } edge[maxm * 2]; int n, m; int head[maxn]; int q[maxn]; bool vis[maxn]; int cur[maxn]; int dep[maxn]; int ncount; int path[maxn]; void addedge(int a, int b, int f) { edge[ncount].v = b; edge[ncount].f = f; edge[ncount].next = head[a]; head[a] = ncount++; } void input() { ncount = 0; memset(head, -1, sizeof(head)); for (int i = 0; i < m; i++) { int a, b, f; scanf("%d%d%d", &a, &b, &f); a--; b--; addedge(a, b, f); addedge(b, a, 0); } } void bfs(int s, int t) { memset(vis, 0, sizeof(vis)); memset(dep, -1, sizeof(dep)); int front = 0, rear = 0; q[rear++] = s; vis[s] = true; dep[s] = 0; while (front != rear && !vis[t]) { int u = q[front++]; for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].v; if (!vis[v] && edge[i].f > 0) { q[rear++] = v; vis[v] = true; dep[v] = dep[u] + 1; } } } } int dinic(int s, int t) { int ret = 0; while (true) { bfs(s, t); if (dep[t] == -1) break; int path_n = 0; int x = s; memcpy(cur, head, sizeof(cur)); while (true) { if (x == t) { int mink = -1, delta = inf; for (int i = 0; i < path_n; ++i) { if (edge[path[i]].f < delta) { delta = edge[path[i]].f; mink = i; } } for (int i = 0; i < path_n; ++i) { edge[path[i]].f -= delta; edge[path[i] ^ 1].f += delta; } ret += delta; path_n = mink; if (path_n) x = edge[path[path_n - 1]].v; else x = s; } int e; for (e = cur[x]; ~e; e = edge[e].next) { if (edge[e].f == 0) continue; int y = edge[e].v; if (dep[x] + 1 == dep[y]) break; } cur[x] = e; if (~e) { path[path_n++] = e; x = edge[e].v; } else { if (path_n == 0) break; dep[x] = -1; --path_n; if (path_n) x = edge[path[path_n - 1]].v; else x = s; } } } return ret; } int main() { //freopen("t.txt", "r", stdin); while (~scanf("%d%d", &m, &n)) { input(); printf("%d ", dinic(0, n - 1)); } return 0; }