HDu 3549(最大ストリーム)
10442 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3549
最大ストリームの基礎問題.
View Code
最大ストリームの基礎問題.
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
",SAP(1,n));
68 }
69 return 0;
70 }
71
72
73
74