hdu 3549(最大流）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3549
最大流基础题。
View Code
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define MAXN 22
 6 #define inf 1<<28
 7 int map[MAXN][MAXN];
 8 int pre[MAXN];
 9 int level[MAXN];
10 int gap[MAXN];
11 
12 int SAP(int vs,int vt){
13     memset(pre,-1,sizeof(pre));
14     memset(level,0,sizeof(level));
15     memset(gap,0,sizeof(gap));
16     int v,u=pre[vs]=vs,maxflow=0,aug=inf;
17     gap[0]=vt;
18     while(level[vs]<vt){
19         for(v=1;v<=vt;v++){
20             if(map[u][v]>0&&level[u]==level[v]+1){
21                 break;
22             }
23         }
24         if(v<=vt){
25             pre[v]=u;
26             u=v;
27             if(v==vt){
28                 aug=inf;
29                 for(int i=v;i!=vs;i=pre[i]){
30                     if(aug>map[pre[i]][i])aug=map[pre[i]][i];
31                 }
32                 maxflow+=aug;
33                 for(int i=v;i!=vs;i=pre[i]){
34                     map[pre[i]][i]-=aug;
35                     map[i][pre[i]]+=aug;
36                 }
37                 u=vs;
38             }
39         }else {
40             int minlevel=vt;
41             for(v=1;v<=vt;v++){
42                 if(map[u][v]>0&&minlevel>level[v]){
43                     minlevel=level[v];
44                 }
45             }
46             gap[level[u]]--;
47             if(gap[level[u]]==0)break;
48             level[u]=minlevel+1;
49             gap[level[u]]++;
50             u=pre[u];
51         }
52     }
53     return maxflow;
54 }
55 
56 int main(){
57     int _case,t=1,n,m,u,v,cap;
58     scanf("%d",&_case);
59     while(_case--){
60         memset(map,0,sizeof(map));
61         scanf("%d%d",&n,&m);
62         while(m--){
63             scanf("%d%d%d",&u,&v,&cap);
64             map[u][v]+=cap;
65         }
66         printf("Case %d: ",t++);
67         printf("%d\n",SAP(1,n));
68     }
69     return 0;
70 }
71         
72 
73 
74