poj 3436 ACM Computer Factory sap+输出方案

缘起

以前做的最大流的题目都是求最大流, 求出就可以了. 输出方案的并不多. 本题不仅仅求出最大流, 而且将方案也输出了。 poj 3436 ACM Computer Factory

分析

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
流水线上有N台机器装电脑，电脑有P个部件，每台机器有三个参数，产量，输入规格，输出规格;
输入规格中0表示该部件不能有，1表示必须有，2无所谓;
输出规格中0表示该部件没有，1表示有。
问如何安排流水线（如何建边）使产量最高。

【输入】
输入由N和P构成. 然后是对机器的N个描述. 第i个机器的描述包含2P+1个整数. 
Qi Si,1 Si,2...Si,P Di,1 Di,2...Di,P
其中Qi是产量. Si,j（1<=j<=P）表明输入要求, Di,j(1<=j<=P)是表示产出要求.
1 ≤ P ≤ 10, 1 ≤ N ≤ 50, 1 ≤ Qi ≤ 10000

【输出】
首先输出最多能装几台机器. 然后输出能达到这个最高产量的拓扑必须要建立的弧的数量M. 然后输出M行.
格式为 A B W, 表示A将交付W台机器给到B

【样例输入】
Sample input 1
3 4
15  0 0 0  0 1 0
10  0 0 0  0 1 1
30  0 1 2  1 1 1
3   0 2 1  1 1 1
Sample input 2
3 5
5   0 0 0  0 1 0
100 0 1 0  1 0 1
3   0 1 0  1 1 0
1   1 0 1  1 1 0
300 1 1 2  1 1 1
Sample input 3
2 2
100  0 0  1 0
200  0 1  1 1

【样例输出】
Sample output 1
25 2
1 3 15
2 3 10
Sample output 2
4 5
1 3 3
3 5 3
1 2 1
2 4 1
4 5 1
Sample output 3
0 0

【限制】
1s

【是否接受特判】
是

又是最大流的拆点构图. 将每台电脑拆点成为2个网络流中的点. 第一个点是输入前的状态A. 第二个点是输出之后的状态B. 拆出的两个点之间连接弧容量是此机器的产出效率. 而一开始双重for循环遍历处理出哪些机器后续能接上哪些机器（即哪些机器的输出可以作为另一台机器的输入, 所以图中的弧一定是某机器的B拆点连上某机器的A拆点）. 则它们之间连接弧，弧的容量是inf（你想想看，不影响的, 因为A->B的容量限制住了）.

然后建立炒鸡源和炒鸡汇. 炒鸡源到状态为不包含1的点连弧容量为inf. 而能到炒鸡汇的只能是最后全部是1的节点. 弧的容量是inf. inf都是没关系的, 因为A到B的弧的容量已经限制住了.

然后在这张图上跑最大流. 但是本题需要输出最大流的方案. 任何一种都行. 所以自然我们需要去看残余网络. 即去看最初建图的每一条弧（即h,而不是 h^1）. 此题就要我们明白残余网络意味着什么. 其实在【1】中讲到残余网络的定义就知道了，我们只需要看看每条弧（h而不是h^1）相比初始的inf容量减少了多少，就知道此弧通过了多少的流量. 而且我们只需要处理一组数据就行了.

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

struct Machine
{
	int q, s[15], d[15];
}m[55];

int n,p,M, t, head[55<<1],cnt, inf = 0x3f3f3f3f, pre[55<<2], flow[55<<1], level[55<<1], gap[55<<1], start;

struct Arc
{
	int from, to, nxt, cap;
}g[55+55*55<<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++;
}

bool no1(int i) // 如果m[i]这台机器的输入没有1
{
	for (int j =1; j<=p; j++)
	{
		if (m[i].s[j]==1)
		{
			return false;
		}
	}
	return true;
}

bool all1(int i) // 如果m[i]这台机器的输出都是1
{
	for (int j = 1; j<=p ;j++)
	{
		if (m[i].d[j]!=1)
		{
			return false;
		}
	}
	return true;
}

bool match(int i, int j) // 机器i的输出能否成为机器j的输入
{
	if (i==j)
	{
		return false;
	}
	for (int x = 1; x<=p; x++)
	{
		if (m[j].s[x]==1 && !m[i].d[x] || !m[j].s[x] && m[i].d[x]) // 如果机器j要求有,但是机器i没提供或者机器j要求不能有但是机器i提供了, 则都返回false
		{
			return false;
		}
	}
	return true;
}

void build()
{
	for (int i = 1; i<=n; i++)
	{
		if (no1(i))
		{
			addArc(0, i, inf);
		}
	} // 炒鸡源到i的弧
	for (int i = 1; i<=n; i++)
	{
		addArc(i, i+n, m[i].q);
	} // 同一台机器的输入到输出的弧
	for (int i = 1; i<=n; i++)
	{
		if (all1(i))
		{
			addArc(n+i, t, inf);
		}
	} // 输出到炒鸡汇
	start = cnt; // 将考察g[start, ..., cnt-1]这些弧
	for (int i = 1; i<=n; i++)
	{
		for (int j = 1; j<=n; j++) // 机器i的输出到机器j的输入
		{
			if (match(i,j))
			{
				addArc(i+n,j,inf);
			}
		}
	}
}

int feasible(int cur)
{
	for (int h = head[cur], to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (g[h].cap>0 && level[cur]==level[to]+1)
		{
			return h;
		}
	}
	return -1;
}

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 retreat(int cur)
{
	int ans = t+1;
	for (int h = head[cur],to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (g[h].cap>0 && ans>level[to]+1)
		{
			ans = level[to]+1;
		}
	}
	return ans;
}

int sap(int s,int t)
{
	memset(level, 0, sizeof(level));
	memset(gap, 0, sizeof(gap));
	int ans =0, cur = s, nxt, nxtArc;
	flow[s] = inf;
	while(level[s]<=t)
	{
		nxtArc = feasible(cur);
		if (~nxtArc)
		{
			nxt = g[nxtArc].to;
			pre[nxt] = nxtArc;
			flow[nxt] = min(flow[cur], g[nxtArc].cap);
			cur = nxt;
			if (cur==t)
			{
				ans+=flow[t];
				updata(s,t,flow[t]);
				cur = s;
			}
		}
		else
		{
			if (!--gap[level[cur]])
			{
				return ans;
			}
			gap[level[cur]=retreat(cur)]++;
			if (cur!=s)
			{
				cur = g[pre[cur]].from;
			}
		}
	}
	return ans;
}

struct Ans
{
	int from,to,flow;
}ans[55*55<<1];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &p, &n);
	memset(head, -1, sizeof(head));
	t = n*2+1; // 炒鸡汇, 假设[1,...,n]是n台机器的输入状态, [n+1,...,2n]是n台机器的输出状态,0是炒鸡源, t是炒鸡汇
	for (int i = 1; i<=n; i++)
	{
		scanf("%d", &m[i].q);
		for (int j = 1;j<=p; j++)
		{
			scanf("%d", &m[i].s[j]);
		}
		for (int j = 1;j<=p; j++)
		{
			scanf("%d", &m[i].d[j]);
		}
	} // 读入m台机器的数据
	build(); // 建图
	int maxflow = sap(0,t); // 跑最大流
	for (int h = start; h<cnt; h+=2)
	{
		if (g[h].cap<inf) // 说明此弧上跑了流量
		{
			ans[M].from = g[h].from;
			if (ans[M].from>n)
			{
				ans[M].from-=n;
			}
			ans[M].to = g[h].to;
			if (ans[M].to>n)
			{
				ans[M].to-=n;
			}
			ans[M].flow = inf-g[h].cap; // 容量的减少就是流量(根据对残余网络的理解)
			M++;
		}
	}
	printf("%d %d\n", maxflow, M);
	for (int i = 0; i<M; i++)
	{
		printf("%d %d %d\n", ans[i].from, ans[i].to, ans[i].flow);
	}
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 144kB
Length 3607
Lang C++
Submitted 2019-09-29 21:39:48
Shared
RemoteRunId 20911407

参考

【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/