首页 > 代码库 > POJ 1273(EK)

POJ 1273(EK)

2024-07-06 00:44:54   223人阅读

题目大概意思是，有N条水沟和M个水池,问从第一个水池到最后一个水池在同一时间内能够流过多少水
第一行有两个整数N,M
接下来N行,每行有3个整数,a,b,c,代表从a到b能够流c单位的水
超级模板题,一个有向图,源点为1,汇点为M,套最大流模板就行了

我就通过这水题理解EK的...

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<queue>
 5 #include<climits>
 6 using namespace std;
 7 #define N 210
 8 #define clr(a,b) memset(a,b,sizeof(a))
 9 int cap[N][N];///容量
10 int n,m;
11 int a,b,c;
12 int EK(int s,int t)///s代表源点，t代表汇点
13 {
14     queue<int> q;
15     int flow[N][N];///流量
16     int low[N];///low[v]表示s-v的最小残量
17     int pre[N];///用于BFS寻找父亲节点
18     int u,v;
19     int maxflow = 0;///最大流
20     clr(flow,0);///初始时残量网络为0
21     while(1)
22     {
23         q.push(s);///把源点压入队列中
24         clr(low,0);
25         low[s] = INT_MAX;
26         while(!q.empty())
27         {
28             u = q.front();
29             q.pop();
30             for(v = 0; v <= t; v ++)
31             {
32                 if(!low[v] && cap[u][v] > flow[u][v])///找到新节点v
33                 {
34                     q.push(v);
35                     low[v] = min(low[u], cap[u][v] - flow[u][v]);
36                     pre[v] = u;
37                 }
38             }
39         }
40         if(low[t] == 0) break;///找不到，则当前流已经是最大
41         for(u = t; u != s; u = pre[u])
42         {
43             flow[pre[u]][u] += low[t];
44             flow[u][pre[u]] -= low[t];
45         }
46         maxflow += low[t];
47     }
48     return maxflow;
49 }
50 int main()
51 {
52     int ans;
53     while(~scanf("%d%d",&n,&m))
54     {
55         clr(cap,0);
56 
57         for(int i=0; i<n; i++)
58         {
59             scanf("%d%d%d",&a,&b,&c);
60             cap[a][b] += c;
61         }
62         ans = EK(1,m);
63         printf("%d\n",ans);
64     }
65     return 0;
66 }

 


联系
我们