虽然算法还没有理解透，但以及迫不及待地想要A道题了。
非常裸的最大流，试试lrj的模板练练手。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #include <queue> 6 using namespace std; 7 8 const int maxn = 200 + 10; 9 const int INF = 1000000000; 10 11 struct Edge 12 { 13 int from, to, cap, flow; 14 Edge(int u, int v, int c, int f):from(u), to(v), cap(c), flow(f) {} 15 }; 16 17 int n, m, M; 18 vector<Edge> edges; 19 vector<int> G[maxn]; 20 int a[maxn]; //到起点i的可改进量 21 int p[maxn]; //最短路数上p的入弧编号 22 23 void Init(int n) 24 { 25 for(int i = 0; i < n; ++i) G[i].clear(); 26 edges.clear(); 27 } 28 29 void AddEdge(int from, int to, int cap) 30 { 31 edges.push_back(Edge(from, to, cap, 0)); 32 edges.push_back(Edge(to, from, 0, 0)); //反向弧 33 m = edges.size(); 34 G[from].push_back(m-2); 35 G[to].push_back(m-1); 36 } 37 38 int MaxFlow(int s, int t) 39 { 40 int flow = 0; 41 for(;;) 42 { 43 memset(a, 0, sizeof(a)); 44 queue<int> Q; 45 Q.push(s); 46 a[s] = INF; 47 while(!Q.empty()) 48 { 49 int x = Q.front(); Q.pop(); 50 for(int i = 0; i < G[x].size(); ++i) 51 { 52 Edge& e = edges[G[x][i]]; 53 if(!a[e.to] && e.cap > e.flow) 54 { 55 p[e.to] = G[x][i]; 56 a[e.to] = min(a[x], e.cap-e.flow); 57 Q.push(e.to); 58 } 59 } 60 if(a[t]) break; 61 } 62 if(!a[t]) break; 63 for(int u = t; u != s; u = edges[p[u]].from) 64 { 65 edges[p[u]].flow += a[t]; 66 edges[p[u]^1].flow -= a[t]; 67 } 68 flow += a[t]; 69 } 70 return flow; 71 } 72 73 int main() 74 { 75 freopen("in.txt", "r", stdin); 76 77 while(scanf("%d%d", &M, &n) == 2) 78 { 79 Init(n); 80 int u, v, c; 81 for(int i = 0; i < M; ++i) 82 { 83 scanf("%d%d%d", &u, &v, &c); 84 AddEdge(u-1, v-1, c); 85 } 86 printf("%d ", MaxFlow(0, n-1)); 87 } 88 89 return 0; 90 }