HDU 3549 Flow Problem 解题报告（EK）算法

转载请注明出处：http://write.blog.csdn.net/postlist

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3549

这是一题裸的网络流题目。说有1000条边，可是只有十五个点，所以实际的边数最多只有15*15。EK复杂度O(VE^{2)，5秒的时间、太多了！}

可是，可是！！ 就是这题搞的我很悲伤，几次TLE+WA+RE。。。。前天想到昨天近十二点，终于找到错误！

先贴上第一次错误代码：

[cpp] view plaincopy

1. #include<iostream>
2. #include<algorithm>
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include<string.h>
6. #include<queue>
7. #include<math.h>
8. #define MAXN 20
9. #define INF 1000
10. #define MIN(x,y) (x<y?x:y)
11. using namespace std;
12. int map[MAXN][MAXN];
14. int maxflow(int num,int map[][MAXN],int s,int t)
15. {
16. int flow[MAXN][MAXN],max_flow[MAXN],fa[MAXN],myqueue[MAXN];
17. int i,j,temp,qfront,qend,ans=0;
18. memset(flow,0,sizeof(flow));
19. while(1)
20. {
21. qfront=qend=0;
22. myqueue[qend++]=s;
23. fa[s]=-2;
24. max_flow[s]=INF;
25. memset(fa,-1,sizeof(fa));
26. while(qfront<qend)
27. {
28. temp=myqueue[qfront++];
29. for(i=0;i<num;i++) if(fa[i]==-1 && map[temp][i]>flow[temp][i])
30. {
31. fa[i]=temp;
32. myqueue[qend++]=i;
33. max_flow[i]=MIN(max_flow[temp],map[temp][i]-flow[temp][i]);
34. }
35. if(fa[t]!=-1)
36. {
37. int k=t;
38. while(fa[k]>=0)
39. {
40. flow[fa[k]][k]+=max_flow[t];//在这，应该加flow[k][fa[k]]-=max_flow[t];
41. k=fa[k];
42. }
43. break;
44. }
45. }
46. if(fa[t]==-1) return ans;
47. else ans+=max_flow[t];
48. }
49. }
51. int main()
52. {
53. int i,j,n,m,t,a,b,c;
54. scanf("%d",&t);
55. for(j=1;j<=t;j++)
56. {
57. memset(map,0,sizeof(map));
58. scanf("%d%d",&n,&m);
59. for(i=0;i<m;i++)
60. {
61. scanf("%d%d%d",&a,&b,&c);
62. map[a-1][b-1]+=c;
63. }
64. int ans=maxflow(n,map,0,n-1);
65. printf("Case %d: %d\n",j,ans);
66. }
67. return 0;
68. }

然后总结下错误原因：1、TLE：while（1）下面第四行，先赋值fa[s]=-2,再memset(fa,0,sizeof(fa));导致后面找到增广路后记录flow直接死循环(实在不知道为什么，求解)。 2、wa：记录flow时也应该记录相应的反向边！

下面贴上正解：

[cpp] view plaincopy

1. #include<iostream>
2. #include<algorithm>
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include<string.h>
6. #include<queue>
7. #include<math.h>
8. #define MAXN 20
9. #define INF 1000
10. #define MIN(x,y) (x<y?x:y)
11. using namespace std;
12. int map[MAXN][MAXN];
14. int maxflow(int num,int map[][MAXN],int s,int t)
15. {
16. int flow[MAXN][MAXN],max_flow[MAXN],fa[MAXN],myqueue[MAXN];
17. int i,j,temp,qfront,qend,ans=0;
18. memset(flow,0,sizeof(flow));
19. while(1)
20. {
21. qfront=qend=0;
22. myqueue[qend++]=s;
23. max_flow[s]=INF;
24. memset(fa,-1,sizeof(fa));
25. fa[s]=-2;
26. while(qfront<qend)
27. {
28. temp=myqueue[qfront++];
29. for(i=0;i<num;i++) if(fa[i]==-1 && map[temp][i]>flow[temp][i])
30. {
31. fa[i]=temp;
32. myqueue[qend++]=i;
33. max_flow[i]=MIN(max_flow[temp],map[temp][i]-flow[temp][i]);
34. }
35. }
36. if(fa[t]!=-1)
37. {
38. int k=t;
39. while(fa[k]!=-2)
40. {
41. flow[fa[k]][k]+=max_flow[t];
42. flow[k][fa[k]]-=max_flow[t];
43. k=fa[k];
44. }
45. }
46. if(fa[t]==-1) return ans;
47. else ans+=max_flow[t];
48. }
49. }
51. int main()
52. {
53. int i,j,n,m,t,a,b,c;
54. scanf("%d",&t);
55. for(j=1;j<=t;j++)
56. {
57. memset(map,0,sizeof(map));
58. scanf("%d%d",&n,&m);
59. for(i=0;i<m;i++)
60. {
61. scanf("%d%d%d",&a,&b,&c);
62. map[a-1][b-1]+=c;
63. }
64. int ans=maxflow(n,map,0,n-1);
65. printf("Case %d: %d\n",j,ans);
66. }
67. return 0;
68. }

应该在宽搜后面加判断是否找到增广路。由于本题WA太久，第一次的AC我是用queue重新敲的。顺便贴上吧，时间差不多。都是一个算法：

[cpp] view plaincopy

1. #include<iostream>
2. #include<algorithm>
3. #include<stdio.h>
4. #include<stdlib.h>
5. #include<string.h>
6. #include<queue>
7. #include<math.h>
8. #define MAXN 20
9. #define INF 0x7fffffff
10. #define MIN(x,y) (x<y?x:y)
11. using namespace std;
12. int flow[MAXN][MAXN],map[MAXN][MAXN],fa[MAXN],a[MAXN];
14. int maxflow(int num,int map[][MAXN],int s,int t)
15. {
16. int ans=0;
17. memset(flow,0,sizeof(flow));
18. while(1)
19. {
20. queue<int> q;
21. q.push(s);
22. memset(a,0,sizeof(a));
23. a[s]=INF;
24. while(!q.empty())
25. {
26. int u=q.front(); q.pop();
27. for(int i=1;i<=num;i++) if(!a[i] && map[u][i]>flow[u][i])
28. {
29. fa[i]=u; q.push(i);
30. a[i]=MIN(a[u],map[u][i]-flow[u][i]);
31. }
32. }
33. if(a[t]==0) break;
34. for(int u=t;u!=s;u=fa[u])
35. {
36. flow[fa[u]][u]+=a[t];
37. flow[u][fa[u]]-=a[t];
38. }
39. ans+=a[t];
40. }
41. return ans;
42. }
44. int main()
45. {
46. int i,j,n,m,t,a,b,c;
47. scanf("%d",&t);
48. for(j=1;j<=t;j++)
49. {
50. memset(map,0,sizeof(map));
51. scanf("%d%d",&n,&m);
52. for(i=0;i<m;i++)
53. {
54. scanf("%d%d%d",&a,&b,&c);
55. map[a][b]+=c;
56. }
57. int ans=maxflow(n,map,1,n);
58. printf("Case %d: %d\n",j,ans);
59. }
60. return 0;
61. }

好了，网络流的诸多算法终于搞定一个，接下来 改进的SAP算法。。。时间不多，加油了cxb ！