[洛谷4142]洞穴遇险 题解
![[洛谷4142]洞穴遇险 题解](https://ksmeow.moe/wp-content/uploads/2018/06/180624a.jpg "180624a")
题目地址：洛谷：【P4142】洞穴遇险 – 洛谷
题目描述
前方有一片沼泽地.
方便地, 我们用一个n × n 的网格图来描述它, 每一个格子代表着沼泽地的一小片区域. 其中(1, 1) 代表网格图的左上角, (n, n) 代表网格图的右下角. 若用X 表示行数, Y 表示列数, 那么X + Y 为奇数的格子有一个危险度VX, Y , X + Y 为偶数的格子的危险度为0.
为了保障人们的安全, 你有m 个长相怪异的大石头, 你可以选一些石头放在网格图上的某些格子上, 石头可以看成一个‘L’ 形的块, 并且占三个格子, 它通过旋转有四种方式供放置, 仅会使得在拐角处的那个格子危险度减为0.
网格图中还有k 个位置是“禁止位置”, 石头的任何部位都不能位于这些格子上, 且这些位置的危险度一定为0.
现在你需要知道放置一些石头后最小的危险度之和是多少. (石头可以不放完)
输入输出格式
输入格式：
从文件marshland.in 中读入数据。
第一行三个整数n; m; k.
接下来n 行每行n 个整数, 表示每个格子的危险度, 保证X + Y 为偶数的格子和禁止位置的格子的危险度为0.
接下来k 行每行2 个整数X; Y , 表示禁止位置的坐标, 注意有可能会出现重复的禁止位置.
输出格式：
输出到文件marshland.out 中
输出一行一个整数代表最小的危险度之和.
输入输出样例
输入样例#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
说明
对于10%的数据，满足n ≤ 4,
对于30%的数据，满足n ≤ 10,
对于100%的数据，满足n ≤ 50,
对于所有的数据，满足0 ≤ m ≤ n^2/3 ; 0 ≤ k ≤ n2; 0 ≤ VX;Y ≤ 10^6.
题解
雅礼集训Day 5 T1，网络流好题。
我们想用对每个有危险度的格子确定一种安排方案，使得有与它有公共边的两个相邻非对位格子被覆盖或者选择不覆盖这个格子，而且数据范围也很网络流，所以可以考虑网络流。
但是无论是用有危险度的格子去匹配方案，还是用方案去匹配有危险度的的格子，都存在一个问题：流量控制在相邻的格子上，然而存在两个需要流量控制的点，不得不把匹配的流量加到2，但是存在可能无法跑满流的情况，这是无法解决的。
我们考虑，假如对于这样一个情况
---- | 1| ------- |DG| 2| -------
其中，DG是有危险度的格子，我们让流量从1流入，流经DG后从2流出，就无需考虑流量2无法满流的情况了。对于石头数m的限制，直接进行m次增广就可以解决这个问题了。需要注意的是，这里要求的是最大费用可行流，需要实时取min。
代码
// Code by KSkun, 2018/6
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
typedef long long LL;
const int MAXN = 5005, INF = 1e9;
struct Edge {
int to, cap, cost, nxt;
} gra[MAXN << 4];
int head[MAXN], tot;
inline void addedge(int u, int v, int cap, int cost) {
gra[tot] = (Edge) {v, cap, cost, head[u]}; head[u] = tot++;
gra[tot] = (Edge) {u, 0, -cost, head[v]}; head[v] = tot++;
}
int f[MAXN], pre[MAXN], pree[MAXN];
LL dis[MAXN];
bool inque[MAXN];
std::queue<int> que;
inline bool spfa(int s, int t) {
memset(f, 0, sizeof(f));
memset(dis, 0x3f, sizeof(dis));
que.push(s); f[s] = INF; dis[s] = 0; inque[s] = true;
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to; inque[v] = false;
if(gra[i].cap && dis[v] > dis[u] + gra[i].cost) {
dis[v] = dis[u] + gra[i].cost;
f[v] = std::min(f[u], gra[i].cap);
pre[v] = u; pree[v] = i;
if(!inque[v]) {
inque[v] = true; que.push(v);
}
}
}
}
return f[t];
}
LL flow, cost;
LL ans;
inline void mcmf(int s, int t) {
while(spfa(s, t)) {
flow += f[t]; cost += 1ll * f[t] * dis[t];
for(int i = t; i != s; i = pre[i]) {
gra[pree[i]].cap -= f[t]; gra[pree[i] ^ 1].cap += f[t];
}
ans = std::min(cost, ans);
}
}
int n, m, k, a[55][55], S, S1, T;
bool forbid[55][55];
inline int num(int x, int y) {
return (x - 1) * n + y;
}
int main() {
freopen("marshland.in", "r", stdin);
freopen("marshland.out", "w", stdout);
memset(head, -1, sizeof(head));
scanf("%d%d%d", &n, &m, &k);
S = 5000; S1 = 5001; T = 5002;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
cost += a[i][j];
}
}
ans = cost;
for(int i = 1, x, y; i <= k; i++) {
scanf("%d%d", &x, &y);
forbid[x][y] = true;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(((i + j) & 1) && !forbid[i][j]) {
addedge(num(i, j), n * n + num(i, j), 1, -a[i][j]);
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(!((i + j) & 1) && !forbid[i][j]) {
if(i & 1) {
addedge(S1, num(i, j), 1, 0);
if(i - 1 >= 1) addedge(num(i, j), num(i - 1, j), 1, 0);
if(i + 1 <= n) addedge(num(i, j), num(i + 1, j), 1, 0);
if(j - 1 >= 1) addedge(num(i, j), num(i, j - 1), 1, 0);
if(j + 1 <= n) addedge(num(i, j), num(i, j + 1), 1, 0);
} else {
addedge(num(i, j), T, 1, 0);
if(i - 1 >= 1) addedge(n * n + num(i - 1, j), num(i, j), 1, 0);
if(i + 1 <= n) addedge(n * n + num(i + 1, j), num(i, j), 1, 0);
if(j - 1 >= 1) addedge(n * n + num(i, j - 1), num(i, j), 1, 0);
if(j + 1 <= n) addedge(n * n + num(i, j + 1), num(i, j), 1, 0);
}
}
}
}
addedge(S, S1, m, 0);
mcmf(S, T);
printf("%lld", ans);
return 0;
}
