POJ1273Drainage Ditches(网络流入门题目）
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#include <cstdlib>using namespace std;const int INF = 0x7fffffff;const int N = 210;int map1[N][N];int link[N];int mi[N];int n, m;//EK算法int bfs(int s) { queue<int> Q; memset(link, 0, sizeof(link)); mi[s] = INF; Q.push(s); int u, v; while(!Q.empty()) { u = Q.front(); Q.pop(); for(v = 2; v <= n; v++) { if(map1[u][v]>0 && !link[v]) { mi[v] = min(mi[u], map1[u][v]); link[v] = u; if(v == n) { return mi[n]; } Q.push(v); } } } return 0;}void work() { int ans, now, pre, x; for(ans = 0; (x = bfs(1))!=0; ans+=x) { now = n; while(now != 1) { pre = link[now]; map1[pre][now] -= x; map1[now][pre] += x; now = pre; } } printf("%d\n", ans);}int main() { int u, v, cost; while(scanf("%d%d", &m, &n) == 2) { memset(map1, 0, sizeof(map1)); for(int i = 0; i < m; i++) { scanf("%d%d%d", &u, &v, &cost); map1[u][v] += cost;//处理重边。 } work(); }}