UVA 820 --- POJ 1273 最大流

2023-10-11 04:30

文章标签 最大 poj 820 uva 1273

本文主要是介绍UVA 820 --- POJ 1273 最大流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

找了好久这两个的区别。。。UVA820 WA了好多次。不过以后就做模板了，可以求任意两点之间的最大流。

UVA 是无向图，因此可能有重边，POJ 1273是有向图，而且是单源点求最大流，因此改模板的时候注意一下。

而且我居然犯了更愚蠢的错误，以为重边的时候需要选最大的，正解应该是累加。。。。

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