USACO Drainage Ditches

基本的网络流。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define MAXNODE 210
005 #define INF (10000000+10)
006
007 typedef struct Qelement
008 {
009     int node;
010     long flow;
011 }Qelement;
012
013 unsigned long cap[MAXNODE][MAXNODE] = {};
014 int M,N;
015
016 void init()
017 {
018     scanf("%d%d\n",&N,&M);
019     int i;
020     int s,e;
021     long c;
022     for(i = 0;i < N;i ++)
023     {
024         scanf("%d%d%ld\n",&s,&e,&c);
025         cap[s][e] += c;   //+=可以解决多条边的问题
026     }
027 }
028
029 int prev[MAXNODE];   //BFS时前一个点的编号
030 Qelement queue[10 * MAXNODE];
031 _Bool visit[MAXNODE];
032 int head,tail;
033
034 void enqueue(int n,int f)
035 {
036     queue[tail].node = n;
037     queue[tail].flow = f;
038     tail ++;
039 }
040
041 Qelement dequeue()
042 {
043     return queue[head ++];
044 }
045
046 unsigned long get_min(unsigned long a,unsigned long b)
047 {
048     if(a < b)    return a;
049     return b;
050 }
051
052 long bfs()    //BFS找增广路
053 {
054     int i;
055     Qelement now;
056     head = tail = 0;
057     memset(visit,0,sizeof(visit));
058     enqueue(1,INF);
059     visit[1] = 1;
060     while(head < tail)
061     {
062         now = dequeue();
063         for(i = 1;i <= M;i ++)
064         {
065             if(!visit[i] && cap[now.node][i] > 0)
066             {
067                 visit[i] = 1;
068                 prev[i] = now.node;
069                 enqueue(i,get_min(cap[now.node][i],now.flow));
070                 if(i == M)
071                 {
072                     return get_min(cap[now.node][i],now.flow);
073                 }
074             }
075         }
076     }
077     return 0;
078 }
079
080
081 void solve_max_flow()
082 {
083     int i;
084     unsigned long maxflow;
085     unsigned long totmax = 0;
086     while(1)
087     {
088         maxflow = bfs();
089         if(maxflow == 0)    break;   //没有增广路，结束
090         totmax += maxflow;
091         for(i = M;i != 1;i = prev[i])
092         {
093             cap[prev[i]][i] -= maxflow;
094             cap[i][prev[i]] += maxflow;
095         }
096     }
097     printf("%ld\n",totmax);
098 }
099
100 int main()
101 {
102     freopen("ditch.in","r",stdin);
103     freopen("ditch.out","w",stdout);
104     init();
105     solve_max_flow();
106     return 0;
107 }