原题:[洛谷P4142]洞穴遇险
我说怎么在哪里见过这道题呢,原来是石家庄二中高一部出的洛谷比赛题......
一道费用流好题,难点在构造图。

题目背景

ZRQ在洞穴中准备采集矿物的时候遇险了!洞穴要塌了

题目来源:zhoutb2333

题目描述

整个洞穴是一个 的方格图,每个格子形如 (X,Y),1X,YN(X,Y),1 \le X,Y \le N 。其中 XX 表示从上到下的行数, YY 表示从左到右的列数。 (1,1)(1,1) 在左上角, (1,N)(1,N) 在右上角, (N,1)(N,1) 在左下角, (N,N)(N,N) 在右下角。

满足 X+YX+Y 为奇数格子的有一个不稳定度 VX,YV_{X,Y}, X+YX+Y 为偶数的格子的不稳定度为 00

ZRQ现在手里恰巧有 MM 个可以支撑洞穴的柱子,柱子的力量可以认为是无穷大。

只要支撑住了一个格子那么这个格子的不稳定度将降为 00

每个柱子是 型的,它除了要占据当前的格子外,还需要占据两个相邻的格子(这三个格子形成 型,可以选择任意方向放置,一共有 个方向)。

img

柱子占据相邻的格子不会降低其不稳定度(换句话说就是柱子只有在拐角处有力量)

有些格子的顶已经塌下来了,无法在其位置放置柱子了,这些格子也不能被占据了。这样已经塌了的格子有 KK 个(他们的不稳定度都为 00 ,即使 X+YX+Y 为奇数,塌下来的格子的不稳定度也会为 00 )。

ZRQ想问你,在放置一些柱子后 ,最小的不稳定度之和为多少(可以不将 MM 个柱子都放完)。

输入输出格式

输入格式:

第一行三个整数 N,M,KN,M,K 接下来 NN 行每行 NN 个整数,表示每个格子的不稳定度,保证 X+YX+Y 为偶数的格子和已经塌下的格子的不稳定度为 00 。 接下来 KK 行每行 22 个整数 X,YX,Y ,表示已经塌下的格子的坐标。

输出格式:

一行一个整数,表示最小的不稳定度的和。

输入输出样例

输入样例#1:

3 3 1
0 1 0
2 0 1
0 1 0
1 3

输出样例#1:

3

输入样例#2:

3 3 4
0 2 0
0 0 4
0 3 0
1 3
2 1
2 2
3 1

输出样例#2:

9

说明

1010 个测试点,每个点 1010 分,计 100100 分。

对于测试点 11 ~ 33 ,有 1N61 \le N \le 6。 对于测试点 44 ~ 77 ,有 1N111 \le N \le 11。 对于测试点 88 ~ 1010 ,有 1N501 \le N \le 50

对于所有测试点, 0MN23,0KN2,0VX,Y1060 \le M \le \frac{N^2}{3}, 0 \le K \le N^2, 0 \le V_{X,Y} \le 10^6

样例#1解释:

显然无法让任意两个不稳定的格子都被拐角覆盖,于是将 (2,1)(2,1) 用拐角覆盖住即可。这样剩余的不稳定度为 V1,2+V2,3+V3,2=1+1+1=3V_{1,2}+V_{2,3}+V_{3,2}=1+1+1=3

样例#2解释:

一个都放不下,这样剩余的不稳定度为 V1,2+V2,3+V3,2=2+4+3=9V_{1,2}+V_{2,3}+V_{3,2}=2+4+3=9

Solution

一道费用流好题。

观察下数据范围,差不多费用流的样子,难点在图的构造。

首先柱子应该放在 x+y 为奇数的格子上(即有不稳定度的格子上)。然后可以观察到每一种放置方案中,连接该格子的相邻格子,它的 x+y 为偶数,并且一个在奇数列,一个在偶数列。我们依此条件建图。

  • 我们考虑 x+y 为奇数的格子,即放置柱子的格子。我们将该点一分为二,分别放在第 2,3 列,连接一条 容量为 1,费用为 Vx,y-V_{x,y} 的边。
  • 其次我们考虑 x+y 为偶数的点
    • 奇数列的点源点 连接一条 容量为 1,费用为 0 的边。向与它相邻的点(有不稳定度的点)连一条 容量为 1,费用为 0 的边。
    • 偶数列的点汇点 连接一条 容量为 1,费用为 0 的边。从与它相邻的点(有不稳定度的点)连一条 容量为 1,费用为 0 的边。
  • 塌了的格子均不连边
  • 定义一个新的源点,向源点连一条 容量为 m,费用为 0 的边。保证总流量不超过 m。
  • 从新的源点向汇点跑最小费用最大流即可。注意跳出条件:如果本次增广源点到汇点的费用为正,直接跳出即可 (不需要保证最大流)。

题解

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
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
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define max(a,b) ((a)>(b)?(a):(b))
const int N = 100000;
inline void read(int &x) {
x=0;int f=1;char ch=getchar();
while(!isdigit(ch)) {if(f=='-')f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}

int cnt=1, nxt[N], head[N], to[N], w[N], flw[N];
inline void add(int u, int v, int flow, int W) {
nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v,flw[cnt]=flow,w[cnt]=W;
nxt[++cnt]=head[v],head[v]=cnt,to[cnt]=u,flw[cnt]=0,w[cnt]=-W;
}

int n, m, k, s, t, num=0, sum=0;
int a[52][52], has[52][52];
int d[4][2]={1,0,-1,0,0,1,0,-1};

int f[7502], vis[7502], pre[7502], last[7502];
queue<int> q;
bool spfa() {
memset(f, 0x3f, sizeof f);
memset(vis, 0, sizeof vis);
q.push(s); f[s]=0;

int u, v;
while(!q.empty()) {
u=q.front(), q.pop(), vis[u]=0;
for(int i=head[u];i;i=nxt[i]) {
v = to[i];
if(flw[i] && f[v]>f[u]+w[i]) {
f[v] = f[u]+w[i];
pre[v] = u;
last[v] = i;
if(!vis[v]) q.push(v), vis[v]=1;
}
}
}
return f[t]<0;
}

int MFMC() {
int cost=0;
while(spfa()) {
cost += -f[t];
for(int p=t;p!=s;p=pre[p]) {
--flw[last[p]];
++flw[last[p]^1];
}
}
return cost;
}

#define check if(x<1||x>n||y<1||y>n||a[x][y]==-1)continue
inline void Build_Graph() {
int x, y; s=0, t=(num+1)<<1;
add(s, t-1, m, 0);
rep(i,1,n)rep(j,1,n)
if(a[i][j]!=-1) {
if((i+j)&1) add(has[i][j], has[i][j]+num, 1, -a[i][j]);
else if(i&1) {
add(t-1, has[i][j], 1, 0);
rep(z,0,3) {
x = i+d[z][0], y = j+d[z][1];
check;
add(has[i][j], has[x][y], 1, 0);
}
}
else {
add(has[i][j], t, 1, 0);
rep(z,0,3) {
x = i+d[z][0], y = j+d[z][1];
check;
add(has[x][y]+num, has[i][j], 1, 0);
}
}
}
}

int main() {
read(n), read(m), read(k); int x, y;
rep(i,1,n)rep(j,1,n) read(a[i][j]),sum+=a[i][j];
rep(i,1,n)rep(j,1,n) has[i][j]=++num;
rep(i,1,k) read(x),read(y), a[x][y]=-1;
Build_Graph();
sum -= MFMC();
printf("%d\n", sum);
return 0;
}