【网络流24题专题】3 · 最小割模型

主要是比较神奇的最小割模型。

涉及的题目有 loj#6007 方格取数loj#6001 太空飞行计划loj#6226 骑士共存问题

方格取数

有一个 $m$ 行 $n$ 列的方格图,每个方格中都有一个正整数。现要从方格中取数,使任意两个数所在方格没有公共边,且取出的数的总和最大,请求出最大的和。

考虑对于方格中,取格子要求“没有公共边”,那么需要想到就是在进行一个黑白染色,不能选与之四连通的格子。所以最后本质上就是一个二分图,不能选有边相连的点,也就是对于每一条边 $\rm e$, 两个端点至多选一个。

然后就是很神奇的建图方式。考虑为了模拟出这个过程,建一个 $\rm S$ 连向所有黑点,流量即为点权;建一个 $\rm T$ 让所有白点连向它,流量同样是点权。中间根据连通性来连流量为 $+\infty$ 的边。这样建模之后,考虑最小割的本质含义。对于一条边 $(u,v)$ ,$\mathrm S\to u$ 和 $v\to\rm T$ 必定有一个需要被割,满足「两个端点至多选一个」的限制。那么如果用最小割的话,就可以将挑出来的边作为删去的点从总权中减去即为答案。

那么大概最小割的建模技巧,就是考虑用连通性这个东西来操作。比如什么「A和B至多选一个使得最终权值最大/小」,就可以用类似的技巧来建模。

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
int map[MAXN][MAXN] ;
int dx[4] = {0, 1, 0, -1} ;
int dy[4] = {1, 0, -1, 0} ;
int main(){
rr int i, j ;
cin >> N >> M ; tot = 1 ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= M ; ++ j)
scanf("%d", &base[++ tot]), Ans += base[tot],
(i + j & 1) ? white[++ w] = tot : black[++ b] = tot, map[i][j] = tot ;
S = 1, T = tot + 1 ; /*cout << tot << endl ;*/
for (i = 1 ; i <= w ; ++ i) Add(S, white[i], base[white[i]]) ;
for (i = 1 ; i <= w ; ++ i) {
int x = ceil((double)(white[i] - 1) / M) ;
int y = (white[i] - 1) - (x - 1) * M ;
// cout << x << " " << y << endl ;
for (j = 0 ; j <= 4 ; ++ j){
int kx = x + dx[j], ky = y + dy[j] ;
if (kx <= 0 || ky <= 0 || ky > M || kx > N) continue ;
Add(white[i], map[kx][ky], INF) ;
}
}
for (i = 1 ; i <= b ; ++ i)
Add(black[i], T, base[black[i]]) ;
cout << Ans - HLPP() << endl ; return 0 ;
}

太空飞行计划

现已确定了一个可供选择的实验集合 $E = \{ E_1, E_2, \cdots, E_m \}$,和进行这些实验需要使用的全部仪器的集合$ I = \{ I_1, I_2, \cdots, I_n \}$。实验 $E_j$ 需要用到的仪器是 $I$ 的子集 $R_j \subseteq I$。

配置仪器 $I_k$ 的费用为 $c_k$ 美元。实验 $E_j$ 的赞助商已同意为该实验结果支付 $p_j$ 美元。W 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。

这个题的模型似乎是什么「最大权闭合子图」,大概就是如果选了某个点 $v$ ,那么 $v$ 指向的所有点都必须要选,最大化点权和。

考虑以这么一种方式建图。$\rm S$ 连向所有正权点,流量为该点的点权;所有负权点连向 $\rm T$ ,流量为该点的绝对值;原本图中的点按照原来的方式连上去,流量为 。跑一个最小割,然后正权点和-最小割就是最终的答案。

考虑这么做的正确性。对于最小割而言,既然是割,那么要么会去割一个正权点,代表正权点连接点集都不选;或者选择割掉与之相连的所有负权点,代表选了这个点集。那么这样两种决策的本质上都是在倒扣代价。所以是成立的。

这题还要憨憨地输出方案。这个地方有个神奇的输出方式,就是判断每个点是否与 $\rm S$ 相连,如果一个点指向的某个点不与 $\rm S$ 连通,那么他就它俩之间的边就是一条割边。

首先不难知道,这些边都是满流的。考虑之所以这些满流的边就是被割的边,原因是他们恰好是 $\rm S$ 到 $\rm T$ 每条路径的瓶颈边,所以他们的流量加起来就是最大流(因为即使有更多也不能流了),那么也就是最小割。

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
int sum ;
int newline ;
int E[M * 2] ;
int read(){
char ch = ' ' ; int res = 0 ;
while (!isdigit(ch)) ch = getchar() ;
while (isdigit(ch))
res = res * 10 + ch - 48 , ch = getchar() ;
if (ch == '\n') newline = 1 ;
return res ;
}
int main(){
int x, y ;
int nn, mm ;
cin >> nn >> mm ;
_s = 0, _t = 100000 ; cnt = -1 ;
memset(head, -1, sizeof(head)) ;
for (int i = 1 ; i <= nn ; ++ i){
x = read() ;
sum += x ; newline = 0 ;
add(_s, i, x) ; add(i, _s, 0) ;
while (!newline){
y = read() ;
add(y + nn, i, 0) ;
add(i, y + nn, 100000000) ;
}
}
for (int i = 1 ; i <= mm ; ++ i)
cin >> y, add(i + nn, _t, y), add(_t, i + nn, 0) ;
n = nn + mm ; res = sum - dinic() ;
for (int i = 1 ; i <= nn ; ++ i)
if (dis[i]) printf("%d ", i) ;
puts("") ;
for (int i = nn + 1 ; i <= mm + nn ; ++ i)
if (dis[i]) printf("%d ", i - nn) ;
return printf("\n%d\n", res), 0 ;
}

骑士共存

给定 $n^2$ 个方格的国际象棋棋盘和障碍标志,有障碍的不能放,计算棋盘上最多可以放置多少个骑士,使得它们彼此互不攻击。

$n\leq 200$

大概这种题一开始被我当作一般图最大独立集做了…然后不会…

感觉在网格图搞事情,还是需要有种观察性质的直觉的。比如就会发现,骑士跳的每两步,都不会是同一个颜色。那么这就会转化成一个二分图问题,同种颜色之间没有边相连,有两种颜色,符合二分图的限制。所以最后只需要求一发二分图最大独立集即可。

考虑把原二分图转为流图,中间的边流量为 inf ,其余为 1 。这个网络的最小割满足,对于中间每一条边,两端的点必定选择了一个,否则 S 与 T 仍连通。故最小割对应最小点覆盖。而最小点覆盖与最大独立集互为对偶问题,所以算一下即可。

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
int main(){
cin >> n >> m ;
int x, y, kx, ky ;
_s = 0, _t = 60001, cnt = -1 ;
memset(head, -1, sizeof(head)) ;
for (int i = 1 ; i <= m ; ++ i)
cin >> x >> y, mark[x][y] = 1 ;
for (x = 1 ; x <= n ; ++ x)
for (y = 1 ; y <= n ; ++ y){
if (mark[x][y]) continue ;
if ((x + y) % 2 == 0){
for (int k = 0 ; k <= 7 ; ++ k){
kx = x + dx[k] ;
ky = y + dy[k] ;
if (mark[kx][ky]) continue ;
if (kx < 1 || ky < 1 || ky > n || kx > n) continue ;
add(kx * (n + 1) + ky, x * (n + 1) + y, 0) ;
add(x * (n + 1) + y, kx * (n + 1) + ky, 100000000) ;
}
//cout << x << " " << y << endl ;
add(x * (n + 1) + y, _s, 0) ;
add(_s, x * (n + 1) + y, 1) ;
}
else{
add(_t, x * (n + 1) + y, 0) ;
add(x * (n + 1) + y, _t, 1) ;
}
}
int t = n ; n = (n + 1) * (n + 1) ;
cout << t * t - m - dinic() << endl ; return 0 ;
}

这个地方大概需要注意,两个点之间不要连双向的边。这样最小割就会错,因为最大流的意义不对了。