Hdu Drainage Ditches

View Code
  1 /*
  2 http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?pid=1001&ojid=0&cid=4456&hide=0
  3 
  4 hdu  Drainage Ditches 
  5 */
  6 #include <iostream>
  7 #include<cstdio>
  8 #include<cstring>
  9 #include<vector>
 10 #include<queue>
 11 #include<algorithm>
 12 using namespace std;
 13 #define min(a,b) ((a)<(b))?(a):(b)
 14 #define max(a,b) ((a)>(b))?(a):(b)
 15 #define MAXN 200
 16 #define MAXM 500
 17 #define INF 0x3f3f3f3f
 18 //链式前向星
 19 struct enode
 20 {
 21     int t;
 22     int w;                //权值
 23     int c;                //流量
 24 //  int cost;
 25 //    int pre;            //前向指针
 26     int next;
 27 };
 28 struct lstar
 29 {
 30     struct enode e[MAXM];
 31     int box[MAXN],ecnt;
 32     //int etail[MAXN];        //尾部
 33     void init()
 34     {
 35         ecnt=0;
 36         memset(box,-1,sizeof(box));
 37     //    memset(etail,-1,sizeof(etail));        //初始化尾部
 38     }
 39     void ins(int f,int t,int c)                   //简单
 40     {
 41         e[ecnt].t=t;
 42     //    e[ecnt].pre=-1;
 43         e[ecnt].next=box[f];
 44         e[ecnt].c=c;
 45         box[f]=ecnt++;
 46     }
 47     void addedge(int f,int t,int c)            //流量重载
 48     {
 49         e[ecnt].next=box[f];
 50         e[ecnt].t=t;
 51         e[ecnt].c=c;
 52         box[f]=ecnt++;
 53         e[ecnt].next=box[t];
 54         e[ecnt].t=f;
 55         e[ecnt].c=0;
 56         box[t]=ecnt++;
 57     }
 58     void ins1(int f,int t,int w)             //权值重载
 59     {
 60         e[ecnt].t=t;
 61         e[ecnt].w=w;
 62         e[ecnt].next=box[f];
 63         box[f]=ecnt++;
 64     }
 65 
 66 };
 67 
 68 int sap(int s,int t,lstar G,int N)//最大流问题
 69 {
 70     int gap[MAXN],lvl[MAXN],cur[MAXN],pre[MAXN];
 71     int curflow,ans=0,u,tmp,neck,i;
 72     memset(lvl,0,sizeof(lvl));
 73     memset(gap,0,sizeof(gap));
 74     memset(pre,-1,sizeof(pre));
 75     for(i=0;i<N;i++)
 76         cur[i]=G.box[i];
 77     gap[0]=N;
 78     u=s;
 79     while(lvl[s]<N)
 80     {
 81         if(u==t)
 82         {
 83             curflow=INF;
 84             for(i=s;i!=t;i=G.e[cur[i]].t)
 85             {
 86                 if(curflow>G.e[cur[i]].c)
 87                 {
 88                     neck=i;
 89                     curflow=G.e[cur[i]].c;
 90                 }
 91             }
 92             for(i=s;i!=t;i=G.e[cur[i]].t)
 93             {
 94                 tmp=cur[i];
 95                 G.e[tmp].c-=curflow;
 96                 G.e[tmp^1].c+=curflow;
 97             }
 98             ans+=curflow;
 99             u=neck;
100         }
101         for(i=cur[u];i!=-1;i=G.e[i].next)
102             if(G.e[i].c && lvl[u]==lvl[G.e[i].t]+1)
103                 break;
104         if(i!=-1)
105         {
106             cur[u]=i;
107             pre[G.e[i].t]=u;
108             u=G.e[i].t;
109         }
110         else
111         {
112             if(--gap[lvl[u]]==0)
113                 break;
114              cur[u]=G.box[u];
115             for(tmp=N,i=G.box[u];i!=-1;i=G.e[i].next)
116                 if(G.e[i].c)
117                     tmp=min(tmp,lvl[G.e[i].t]);
118             lvl[u]=tmp+1;
119             gap[lvl[u]]++;
120             if(u!=s)
121                 u=pre[u];
122         }
123     }
124     return ans;
125 }
126 int main()
127 {
128       int m,n;
129       lstar  s;
130         while(cin>>n>>m)
131         {
132             int a,b,cost;
133            // memset(map,0,sizeof(map));
134            s.init();
135            for(int i=0;i<n;i++)
136             {
137                cin>>a>>b>>cost;
138                s.addedge(a-1,b-1,cost);
139             }//参数含义：源点 汇点 网络结点数量
140             //printf("####\n");
141           /*  for(int i=1;i<=n;i++)
142             {
143                 for(int k=s.box[i];k!=-1;k=s.e[k].next)
144                 cout<<i<< " " <<s.e[k].t<< " " <<s.e[k].c<<endl;
145             }//*/
146             cout<<sap(0,m-1,s,m)<<endl;//最大流问题
147         }
148     return 0;
149 }
图论基础求最大流
建图链式前向星注意构建边结构存容量 C
SAP 求最大流