网络流 24 题 部分水题题解

网络流 24 题 部分题题解

注：代码只给出主程序部分，网络流板子基本相同。

方格取数问题

link

给定 $m$ 行 $n$ 列的网格，每个格中有数，你可以取任意个格子的数，但不能同时取相邻的格子（四联通），求取出数的和的最大值。

$1 \le n,m \le 100$，$1 \le a_{i, j} \le 10^5$。

考虑相邻的格子有什么性质，容易发现相邻的格子横纵坐标和的奇偶性相反。又因为相邻的不能同时取，所以我们可以假定全部格子都取，然后去掉不合法的，这样就很容易构造出网络流模型了：

  • 建立超级源、超级汇，超级源连向所有横纵坐标和为奇数的点，所有横纵坐标和为偶数的点连向超级汇，所有横纵坐标和为奇数的点连向相邻的偶点，用连向源和汇的边代表一个点选或不选；
  • 这时候，如果源和汇联通，说明有一对相邻的点同时取了，这种情况就不和法，因此一个合法的取点方案就是一个网络的割；
  • 考虑边权，因为我们用连向源和汇的边代表一个点选或不选，因此不希望删去中间奇偶点之间的边，所以中间的边边权为正无穷；连向源、汇的边边权自然就是这个点代表的格子中的数，这样，我们求一个最小割，就代表了删去数和最小的网格，使得取的数合法，因此答案就是总和 - 最小割。

CODE 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n = read(), m = read();
S = n * m + 1, T = n * m + 2;

for (int i = 1; i <= n; i ++) {
	for (int j = 1; j <= m; j ++) {
		a[i][j] = read(), c[i][j] = (i - 1) * m + j;
	}
}

for (int i = 1; i <= n; i ++) {
	for (int j = 1; j <= m; j ++) {
		res += a[i][j];
		if ((i + j) & 1) {
			addE(S, c[i][j], a[i][j]);
			if (i > 1) addE(c[i][j], c[i - 1][j], INF);
			if (j > 1) addE(c[i][j], c[i][j - 1], INF);
			if (i < n) addE(c[i][j], c[i + 1][j], INF);
			if (j < m) addE(c[i][j], c[i][j + 1], INF);
		} else addE(c[i][j], T, a[i][j]);
	}
}
while (bfs()) res -= dfs(S, INF);

printf("%d\n", res);

骑士共存问题

link

与上题题面基本相同，只不过改为 $n$ 行 $n$ 列，增加了 $m$ 个无法取数的位置，相邻的定义改为马的移动规则，点权为 $1$。

$1 \le n \le 200$，$0 \le m \le n^2$

马的移动每次横纵坐标共改变 $3$，奇偶性依然不同，可以用上题的方法做。

CODE

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
const int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
const int dy[8] = {-2, 1, -1, 2, 2, 1, -1, -2};

n = read(), m = read();
S = n * n + 1, T = n * n + 2;

for (int i = 1; i <= m; i ++) {
	int x = read(), y = read();
	a[x][y] = 1;
}
for (int i = 1; i <= n; i ++) {
	for (int j = 1; j <= n; j ++) {
		if (a[i][j] == 1) continue;
		if ((i + j) & 1) {
			addE(S, F(i, j), 1);
			for (int k = 0; k < 8; k ++) {
				int x = i + dx[k], y = j + dy[k];
				if (x < 1 || x > n || y < 1 || y > n) continue;
				if (a[x][y] == 1) continue;
				addE(F(i, j), F(x, y), INF);
			}
		} else addE(F(i, j), T, 1);
	}
}

res = n * n - m;
while (bfs()) res -= dfs(S, INF);

printf("%d\n", res);

飞行员配对方案问题

link

求二分图最大匹配并输出方案。

$1 \le n \le 100$

二分图最大匹配不在赘述，求方案也很简单，如果中间一条边选了，那它的剩余流量为零，因此遍历所有变判断即可。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
m = read(), n = read();
S = n + 1, T = n + 2;

for (int i = 1; i <= m; i ++) addE(S, i, 1);
for (int j = m + 1; j <= n; j ++) addE(j, T, 1);

while (true) {
	int x = read(), y = read();
	if (x < 0 && y < 0) break;
	addE(x, y, 1);
}

while (bfs()) res += dfs(S, INF);

printf("%d\n", res);
for (int i = 2; i <= tot; i ++) {
	if (e[i].y == S || e[i ^ 1].y == S) continue;
	if (e[i].y == T || e[i ^ 1].y == T) continue;
	if (e[i].v == 0 && e[i].y > m) {
		printf("%d %d\n", e[i ^ 1].y, e[i].y);
	}
}

星际转移问题

link

$k$ 个人需要从地球到月球，中间有 $n$ 个空间站和 $m$ 艘飞船，每艘飞船有限载人数，按固定循环节在地球、月球和空间站之间行进，行进时间都为 $1$，每个人可以在任意位置乘飞船到其他地方，也可以在某地停留，空间站可以容纳无限的人，求所有人都到月球的最小时间，没有解输出 $0$。

$1 \le n \le 13$，$1 \le m \le 20$，$1 \le k \le 50$

建边很妙的一道题，我感觉比前面的题难度高了一档。首先考虑怎么判断有没有解，并查集即可。

由于 $n​$ 特别小，可以直接枚举答案，判断是否合法。每个空间站一个点很难建图完成网络流的需求，因为会形成环，而且人的选择与时刻有关，不难想到在点上加一个时间刻，然后就有了一个阴间的算法：

  • 三种点，超级源、汇；第 $i$ 个时间刻的地球月球；第 $i$ 个时间刻的空间站 $j$；

  • 三种边：

    • 源点向所有时刻的地球连边，边权正无穷，月球同理连汇点；
    • 所有上一时刻的地月球、空间站向这一时刻的对应点连边，边权正无穷，代表人在原地不动；
    • 按照飞船的行进在一些上一时刻的点和这一时刻的点连边，边权为该飞船的限载，代表人乘飞船到另一地点；

  • 跑最大流，若最大流大于等于人数，即为合法。

这个建图是在是太妙了，建议多看几遍体会网路流的优美之处加深理解。

实现时有些细节要注意，如每次时间加时如果在原图的基础上继续加边，则需累加上次的答案；如果不累加需要把上次做网络流的图备份，因为跑网络流会改变图的结构；题目求的是要几天，而不是第几天到。

CODE

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
n = read(), m = read(), k = read();
S = ++cnt, T = ++cnt;

for (int i = 1; i <= n + 2; i ++) fa[i] = i;
for (int i = 1; i <= m; i ++) {
	h[i] = read(), r[i] = read();
	for (int j = 1; j <= r[i]; j ++) {
		s[i][j] = read();
		if (s[i][j] == 0) s[i][j] = n + 1;
		if (s[i][j] == -1) s[i][j] = n + 2;
		if (j > 1) fa[getF(s[i][j])] = getF(s[i][j - 1]);
	}
}

if (getF(n + 1) != getF(n + 2)) return puts("0"), 0;

int sum = 0;
for (int i = 1; ; i ++) {
	for (int j = 1; j <= n + 2; j ++) {
		c[i][j] = ++ cnt;
		if (i > 1) addE(c[i - 1][j], c[i][j], INF);
	}
	addE(S, c[i][n + 1], INF);
	addE(c[i][n + 2], T, INF);
	if (i == 1) continue;
	for (int j = 1; j <= m; j ++) {
		int t1 = (i - 2) % r[j] + 1;
		int t2 = (i - 1) % r[j] + 1;
		addE(c[i - 1][s[j][t1]], c[i][s[j][t2]], h[j]);
	}
	while (bfs()) sum += dfs(S, INF);
	if (sum >= k) return printf("%d\n", i - 1), 0;
}

试题库问题

link

$n$ 个题目，$k$ 个题目类型，每个类型都需要选出给定数量的题目。每个题目可以属于不同类型的题目，但只能选为一个类型的题目，求是否可行并输出方案。

$2 \le k \le 20$，$k \le n \le 10^3$

一道题只能对应一个类型，这种 “对应” 关系里面可以看出一点最大流的特征。可以想到建立一个这样的网络：

  • 三种点：源汇点、$n$ 个代表题目的点、$k$ 个代表题目类型的点；
  • 三种边：
    • 源点到题目点，边权 $1$，代表一个点选或不选；
    • 类型点到汇点，边权为这个类型需要的题目数；
    • 题目点到类型点，代表这道题目有这个类型，边权唯一。

这样求一下最大流即最大可以选的题目个数，若没达到要求就无解；否则遍历中间题目到类型的边，剩余流量为 $0$ 就说明这个题目作为这个类型选了。

CODE

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
m = read(), n = read();
S = n + m + 1, T = n + m + 2;

for (int i = 1; i <= n; i ++) addE(S, i, 1);
for (int i = 1, x; i <= m; i ++) {
	x = read(), sum += x;
	addE(i + n, T, x);
}
for (int i = 1; i <= n; i ++) {
	int x = read();
	for (int j = 1; j <= x; j ++) {
		addE(i, read() + n, 1);
	}
}

int Mx = 0;
while (bfs()) Mx += dfs(S, INF);
if (Mx < sum) return puts("No Solution!"), 0;

for (int i = 1; i <= tot; i ++) {
	if (e[i].y == S || e[i ^ 1].y == S) continue;
	if (e[i].y == T || e[i ^ 1].y == T) continue;
	if (e[i].y <= n) continue;
	if (e[i].v == 0) vec[e[i].y - n].pb(e[i ^ 1].y);
}
for (int i = 1; i <= m; i ++, puts("")) {
	printf("%d: ", i);
	for (auto j : vec[i]) printf("%d ", j);
}

未完待续。。。

参考：洛谷题解。