hdoj 1532最大流之Drainage Ditches

Drainage Ditches

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4149 Accepted Submission(s): 1929

Problem Description

Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

Input

The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.

Output

For each case, output a single integer, the maximum rate at which water may emptied from the pond.

Sample Input

5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10

Sample Output

50

Source

USACO 93

Recommend

lwg

好几天没有贴代码了多校后就一直没有贴代码这到底是人懒了呢还是人懒了呢思路一般都不喜欢写呵呵可能是自己习惯了吧多说无益

但是至少也该写写思路吧不然别人怎么看的懂你的代码呢是吧！！昨天搞了一天的最大流虽然还不是非常理解但是也差不多了求增广路的时候一直看不懂

后来根据我一边运行一边研究差不多也研究透了其实这样学习也是一种学习方法吧个人观点这题是最简单的最大流

每一次找一条到增广路每一次娶最小值从后面开始更新这样来达到每条路径的最优

匆匆岁月今天貌似还是有多校的比赛还是应该多看看这些呵呵

虽然有点后悔以前没有好好珍惜时间但是对现在来说也未尝不是一件好事有时候真的狠怀疑自己到底适不适合搞ACM 确实打击的次数多了也麻木了

不说这么多了直接贴代码吧呵呵

View Code

  1 /*
  2 #include<stdio.h>
  3 #include<string.h>
  4 const int INF = 1000000000;
  5 const int MAXN = 210;
  6 
  7 int n, m, s, t;
  8 int vis[MAXN], p[MAXN], cap[MAXN][MAXN], flow[MAXN][MAXN];
  9 
 10 int path(int u){
 11   int d;
 12   vis[u] = 1;
 13   if(u == t) return INF;
 14   else for(int v = 1; v <=n; v++)
 15     if(!vis[v] && cap[u][v]>flow[u][v] && (d = path(v)) > 0){
 16       p[v] = u;
 17       return d<cap[u][v]-flow[u][v]?d:cap[u][v]-flow[u][v];
 18   }
 19   return 0;
 20 }
 21 
 22 int main() {
 23   while(~scanf("%d%d", &n, &m)&&(n||m))
 24   {
 25       memset(cap, 0, sizeof(cap));
 26   memset(flow, 0, sizeof(flow));
 27   for(int i = 1; i <=n; i++) {
 28     int u, v, c;
 29     scanf("%d%d%d", &u, &v, &c);
 30     cap[u][v] += c;
 31   }
 32   s = 1;
 33   t = n-1;
 34   int ans = 0;
 35   for(;;) {
 36     memset(vis, 0, sizeof(vis));
 37     int d = path(s);
 38     if(d == 0) break;
 39     for(int u = t; u != s; u = p[u]) {
 40       flow[p[u]][u] += d;
 41       flow[u][p[u]] -= d;
 42     };
 43     ans += d;
 44   }
 45   printf("%d\n", ans);
 46   }
 47 
 48   return 0;
 49 }
 50 
 51 */
 52 
 53 #include<cstdio>
 54 #include<cstring>
 55 #include<queue>
 56 using namespace std;
 57 const int INF = 1000000000;
 58 const int MAXN = 1000;
 59 
 60 int n, m, s, t;
 61 int a[MAXN], p[MAXN], cap[MAXN][MAXN], flow[MAXN][MAXN];
 62 
 63 int main() {
 64   while(~scanf("%d%d", &n, &m)&&(m||n))
 65   {
 66   memset(cap, 0, sizeof(cap));
 67   for(int i = 1; i <= n; i++) {
 68     int u, v, c;
 69     scanf("%d%d%d", &u, &v, &c);
 70     cap[u][v]+= c;
 71   }
 72   s = 1;
 73   t = m;
 74   int ans = 0;
 75 
 76   queue<int> q;
 77   memset(flow, 0, sizeof(flow));
 78   for(;;) {
 79     memset(a, 0, sizeof(a));
 80     a[s] = INF;
 81     q.push(s);
 82     while(!q.empty()) {
 83       int u = q.front(); q.pop();
 84       for(int v = 1; v <= m; v++) if(!a[v] && cap[u][v]>flow[u][v]){
 85         p[v] = u; q.push(v);
 86         a[v] = a[u] < cap[u][v]-flow[u][v]?a[u]:cap[u][v]-flow[u][v];
 87       }
 88     }
 89     if(a[t] == 0) break;
 90     for(int u = t; u != s; u = p[u]) {
 91       flow[p[u]][u] += a[t];
 92       flow[u][p[u]] -= a[t];
 93     }
 94     ans += a[t];
 95   }
 96   printf("%d\n", ans);
 97   }
 98 
 99   return 0;
100 }