poj 1459 Power Network EK

缘起

日常浪费生命~ poj 1459 Power Network

分析

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
题意：给几个发电站(多源)，给几个消耗站(多汇)，再给几个转发点。
发电站只发电，消耗站只消耗电，转发点只是转发电，再给各个传送线的传电能力。
问你消耗站能获得的最多电是多少。

【输入】
多样例. 开始于四个整数0 <= n <= 100 (nodes), 0 <= np <= n (power stations), 0 <= nc <= n 
(consumers), and 0 <= m <= n^2 (power transport lines). 
然后是m个三元组 (u,v)z, u,v表示两个站点的编号——从0开始. z是运力（0 <= z <= 1000 ）
然后是np个二元组, u(z). u是发电站的编号，z是它的发电能力（0 <= z <= 10000）. 然后是nc个二元组 
u(z), u是消耗站的编号 0 <= z <= 10000 是该消耗站的消耗能力. 所有输入都是整数。

【输出】
每个样例输出最大消耗.

【样例输入】
2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20
7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7
         (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5
         (0)5 (1)2 (3)2 (4)1 (5)4

【样例输出】
15
6

【限制】
2s

本题是多源多汇的网络流建图. 这个在算法导论26章中讲过. 只需要建立一个炒鸡源，一个炒鸡汇即可. 然后从炒鸡源到各个发电站的弧的容量是各个发电站的发电能力.各个消耗站到炒鸡汇的弧的容量是各个消耗站的消耗能力. 其他弧正常建弧. 然后跑EK即可. 提示 : 本题有自环~(自环是要跳过的~没意义, 但是就算自环加入, 依旧不会影响算法的正确性而只会影响最大流算法的效率. 重弧和自环都只会影响算法的效率, 而不会致使算法错误)

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
//#define LOCAL

const int maxn = 105, inf = 0x3f3f3f3f;
int n, np, nc, m,head[maxn], cnt, pre[maxn], flow[maxn];
char s[205];

struct Arc
{
	int from,to, nxt, cap;
}g[maxn*maxn<<1];

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

void updata(int s, int t,int d)
{
	int h;
	while(t!=s)
	{
		h = pre[t];
		g[h].cap-=d;
		g[h^1].cap+=d;
		t = g[h].from;
	}
}

int bfs(int s, int t)
{
	queue<int> q;
	memset(pre, -1,sizeof(pre));
	flow[s] = inf;
	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)
{
	int ans = 0;
	while(1)
	{
		int d = bfs(s,t);
		if (!d)
		{
			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%d%d", &n, &np, &nc, &m))
	{
		memset(head, -1, sizeof(head));
		cnt = 0;
		int u,v,z;
		while(m--)
		{
			scanf("%s", s);
			sscanf(s,"(%d,%d)%d", &u, &v, &z); // 带括号和逗号的输入这样搞就可以了
			if (u==v) // 自环不考虑
			{
				continue;
			}
			addArc(u,v,z);
		}
		while(np--)
		{
			scanf("%s", s);
			sscanf(s,"(%d)%d", &u, &z);
			addArc(n, u, z); // n是炒鸡源
		}
		while(nc--)
		{
			scanf("%s", s);
			sscanf(s,"(%d)%d", &u, &z);
			addArc(u, n+1, z); // n+1是炒鸡汇
		}
		printf("%d\n", ek(n,n+1));
	}
	return 0;
}

但是很遗憾，被T掉了.

Status Time Limit Exceeded
Length 1848
Lang G++
Submitted 2019-09-26 12:34:49
Shared
RemoteRunId 20899741

但是我和其他ac代码对拍过. 算法只是慢, 并没有错误的输出. 为什么会慢呢? 其实要想快，无非就是能大踏步的找到增广路径（即增广路径增加的流量d能够大，而不是每次就增广1的流量）。 所以立马就想到了一个优化——相同起点到相同终点的两条弧的容量完全可以合并. 即

左图没有右图有效率. 因为右图可以一次找出8的增广流量, 而左边只能2次（一次3一次5），这无疑增加了bfs的次数. 降低了EK的效率. 所以改进为如下代码

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
//#define LOCAL

const int maxn = 105, inf = 0x3f3f3f3f;
int n, np, nc, m,head[maxn], cnt, pre[maxn], flow[maxn],map[maxn][maxn]; // map[u][v]记录了u->v的弧在g中的索引
char s[205];

struct Arc
{
	int from,to, nxt, cap;
}g[maxn*maxn<<1];

void addArc(int from, int to, int cap)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from], g[cnt].cap = cap;
	head[from] = cnt;
	map[from][to] = cnt; // 记录弧 from->to
	cnt++;
	g[cnt].from = to, g[cnt].to = from, g[cnt].nxt = head[to], g[cnt].cap = 0;
	map[to][from] = cnt; // 记录弧 to->from
	head[to] = cnt;
	cnt++;
}

void updata(int s, int t,int d)
{
	int h;
	while(t!=s)
	{
		h = pre[t];
		g[h].cap-=d;
		g[h^1].cap+=d;
		t = g[h].from;
	}
}

int bfs(int s, int t)
{
	queue<int> q;
	memset(pre, -1,sizeof(pre));
	flow[s] = inf;
	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)
{
	int ans = 0;
	while(1)
	{
		int d = bfs(s,t);
		if (!d)
		{
			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%d%d", &n, &np, &nc, &m))
	{
		memset(head, -1, sizeof(head));
		memset(map, -1, sizeof(map));
		cnt = 0;
		int u,v,z;
		while(m--)
		{
			scanf("%s", s);
			sscanf(s,"(%d,%d)%d", &u, &v, &z);
			if (u==v)
			{
				continue;
			} // 就算自环加入, 依旧ac. 重弧和自环都只会影响算法的效率, 而不会致使算法错误
			if (~map[u][v]) // 如果已经出现过了
			{
				g[map[u][v]].cap+=z;
			}
			else // 否则就要新增弧了
			{
				addArc(u,v,z);
			}
		}
		while(np--)
		{
			scanf("%s", s);
			sscanf(s,"(%d)%d", &u, &z);
			addArc(n, u, z); 
		}
		while(nc--)
		{
			scanf("%s", s);
			sscanf(s,"(%d)%d", &u, &z);
			addArc(u, n+1, z);
		}
		printf("%d\n", ek(n,n+1));
	}
	return 0;
}

ac情况(水过水过~ 但是证明了上面的优化策略是正确的)

Status Accepted
Time 1204ms
Memory 748kB
Length 2061
Lang G++
Submitted 2019-09-26 12:54:45
Shared
RemoteRunId 20899770

多说一句, 其实一般做最大流的题目

  1. 重弧一般使用一个二维矩阵cap来优化, 即对于重弧i->j, 完全可以 cap[i][j]++, 而不是像本题那样笨拙的使用一个map（也是个二维数组,所以没有空间复杂度优势）来记录弧在g（链式向前星构图）中的索引.

  2. 自环一般不加入流网络构图.

  3. 陈小玉老师的《趣学算法》7.3节以及算法导论26章P430都强调了图中没有反向平行弧, 即弧u->v 存在于原图G中的话, 则v->u就不存在于G中. 但是和重弧、自环一样, 不影响算法的正确性，只影响算法的效率. 所以算法导论和《趣学算法》开宗明义的做了约定——有向带权图中不存在反向平行弧. 甚至《趣学算法》中就将

    包含一个无反向平行弧的有向带权图称之为网络