poj 1273 Drainage Ditches EK模板题 最大流

缘起

【1】中讲解了最大流的FK算法. 本文介绍最大流的EK算法——其实就是将FK算法中找增广路径的dfs改成了bfs 而已. 这一点在【1】中已经说过了. poj 1273 Drainage Ditches

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
题意描述：现在有m个池塘(从1到m开始编号,1为源点,m为汇点),及n条水渠（有向）,
给出这n条水渠所连接的池塘和所能流过的水量,求水渠中所能流过的水的最大容量.

【输入】
多样例
每个样例开始于N和M(0 <= N <= 200,2 <= M <= 200). 然后n行，每行三个整数(s,e,c)
1 <= S, E <= M, 0 <= C <= 10,000,000,c是容量.

【输出】
对每个样例，输出最大流

【样例输入】
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

【样例输出】
50

【限制】
1s

经典的最大流模板题. 用本题展示ek算法. 其实完全就在【1】的基础上改即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxm = 205;
int n,m,head[maxm],cnt, pre[maxm], flow[maxm]; // pre和flow用于bfs记录增广路径,flow[i]是从源点s到i的流量.pre[i]表示来到i是通过哪条边(同时用于bfs判重,即可以表示这个节点有没有访问过),flow的作用在于求出一条增广路之后, 此增广路中的流量d就知道了, 不需要再次沿着此增广路走一遍求出该增广路为最大流增加的流量d.

struct Arc
{
	int from, to, nxt,cap;
}g[maxm*maxm];

void addArc(int u, int v, int w)
{
	g[cnt].from = u, g[cnt].to = v, g[cnt].nxt = head[u], g[cnt].cap = w;
	head[u] = cnt++;
	g[cnt].from = v, g[cnt].to = u, g[cnt].nxt = head[v], g[cnt].cap = 0;
	head[v] = cnt++;
}

void updata(int s,int t, int d) // 更新残余网络——找到了增广流量d
{
	int x,h;
	while(t!=s)
	{
		h = pre[t]; // 通过g[h]抵达t
		g[h].cap-=d;
		g[h^1].cap+=d;
		t = g[h].from;
	}
}

int bfs(int s, int t) // bfs跑残余网络中找增广路径
{
	queue<int> q;
	memset(pre, -1, sizeof(pre)); // 因为pre存的是弧的编号,而弧的编号从0开始的,所以要用-1填充不能用0
	flow[s] = 0x3f3f3f3f;
	q.push(s);
	while(!q.empty())
	{
		int front = q.front();
		q.pop();
		if (front==t)
		{
			updata(s,t,flow[t]);
			return flow[t]; // 找到了增广路径,退出之前修改残余网络
		}
		for (int h = head[front],to; ~h; h = g[h].nxt)
		{
			to = g[h].to;
			if (!~pre[to] && g[h].cap>0)
			{
				pre[to] = h;
				flow[to] = min(flow[front], g[h].cap); // 短板效应
				q.push(to);
			}
		}
	}
	return 0; // 没找到增广路径
}

int ek(int s, int t) // 求s到t的最大流的ek算法
{
	int ans = 0;
	while(1)
	{
		int d = bfs(s,t); // 每次bfs得到的增广路径
		if (d<=0) // 找不到增广路径了
		{
			return ans;
		}
		ans+=d;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\ac.out", "w", stdout);
#endif
	while(~scanf("%d%d", &n, &m))
	{
		memset(head, -1, sizeof(head));
		cnt = 0;
		while(n--)
		{
			int s,e,c;
			scanf("%d%d%d", &s, &e, &c);
			if (s!=e) // 自己到自己不能加, 否则死循环
			{
				addArc(s,e,c);
			}
		}
		printf("%d\n", ek(1,m));
	}
	return 0;
}

代码几乎和【1】延续了一样的风格.

ac情况

20898362 yfsyfs 1273 Accepted 528K 0MS G++ 1825B 2019-09-25 21:32:53

这里多说一句，这里的bfs是搜索可行路径，而不是最短路径. bfs搜索可行路径是可以的. 不要担心可行路径被埋没. 因为如果能到达的话, 则一定能到的.

参考

【1】https://yfsyfs.github.io/2019/09/20/%E6%B4%9B%E8%B0%B7-3376-%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E7%BD%91%E7%BB%9C%E6%9C%80%E5%A4%A7%E6%B5%81-Ford-Fulkerson%E7%AE%97%E6%B3%95/