闲人の题解 P3866

violet

文章标签

首页

归档

标签

关于

友人帐

载入天数...

载入时分秒...

总访问量: | 访问人数:

2021-11-20

5 min read

题解网络流

闲人の题解 P3866

又是一道网络流的建图题
题目传送门

题目分析

有一群敌人“0”，想要走出地图。
有一些障碍“-1”，在地图上。
你可以通过用炸药把一些地变为障碍，不过每一块地变成障碍所需的炸药不同，具体是这块地的数字，如“2”。
你现在要知道阻止敌人走出地图所用的最少炸药是多少。
对100%的数据， $1 \le M,N \le 30$

思路

我们要割断敌人的路，断了的路不能走，又要使所用的炸药最少，想到了什么？
对！最小割！
又因为最大流=最小割。
所以建图+拆点+最大流就是正解。

亿点问题

万恶的建图总是我们成功路上的绊脚石，所以我们应该如何建图呢？
地图上唯一在在动的是敌人，而我们要阻止他到边界。每一个块地有一个值，代表我们那至少要用多少炸药把它变成障碍（要花费多少把流割断）。
那么图的基本框架就出来了：

把所有的点拆成两个，中间连起来的流量为这个点的数值。
构建一个超级源点，把所有的敌人的入点连起来。
把所有的点的出点连上旁边点的入点。
建一个超级汇点，把所有的边界点的出点连起来。

PS.不过敌人和障碍都可以不连边，因为他们不能炸掉。

代码

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;

const int N = 100010, M = 2000010, INF = 1e8;

ll n, m, S, T;
ll head[N], ver[M], edge[M], next_[M], tot;
ll q[N], d[N], cur[N];
ll map[35][35];

ll min_(int x, int y) {
	if (x < y) return x;
	return y;
}

//网络流连边 
void add(int x, int y, int z) {
	ver[tot] = y, edge[tot] = z, next_[tot] = head[x], head[x] = tot ++;
	ver[tot] = x, edge[tot] = 0, next_[tot] = head[y], head[y] = tot ++;
}

//网络流Dinic
bool bfs() {												
	int hh = 0, tt = 0;
	memset(d, -1, sizeof d);
	q[0] = S, d[S] = 0, cur[S] = head[S];
	while (hh <= tt) {
		int t = q[hh++];
		for (int i = head[t]; ~i; i = next_[i]) {
			int ver_ = ver[i];
			if (d[ver_] == -1 && edge[i]) {
				d[ver_] = d[t] + 1;
				cur[ver_] = head[ver_];						
				if (ver_ == T) return true;
				q[++ tt] = ver_;
			}
		}
	}
	return false;   
}

int find(ll u, ll limit) {									
	if (u == T) return limit;
   	ll flow = 0;
	for (int i = cur[u]; ~i && flow < limit; i = next_[i]) {
		cur[u] = i;
		int ver_ = ver[i];
		if (d[ver_] == d[u] + 1 && edge[i]) {
			int t = find(ver_, min_(edge[i], limit - flow));
			if (!t) d[ver_] = -1;
			edge[i] -= t, edge[i ^ 1] += t, flow += t;
		}
	}
	return flow;
}

ll dinic() {												 
	long long r = 0, flow;
	while (bfs()) while (flow = find(S, INF)) r += flow;
	return r;
} 


int main() {
	cin >> n >> m;
	memset(head, -1, sizeof head);																							//初始化表头 
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			cin >> map[i][j];
		}
	}
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			if(map[i][j] == -1) continue;																					//障碍 
			else if(map[i][j] == 0) add((i - 1) * m + j ,(i - 1) * m + j + n * m, INF), add(0, (i - 1) * m + j, INF);		//敌人 
			else add((i - 1) * m + j, (i - 1) * m + n * m + j, map[i][j]);													//自己的入点连出点 
			if(i > 1 && map[i - 1][j] != -1) add((i - 1) * m + n * m + j, (i - 1 - 1) * m + j,INF);							//内部点连四周 
			if(j > 1 && map[i][j - 1] != -1) add((i - 1) * m + n * m + j, (i - 1) * m + j - 1,INF);
			if(i < n && map[i + 1][j] != -1) add((i - 1) * m + n * m + j, (i) * m + j,INF);
			if(j < m && map[i][j + 1] != -1) add((i - 1) * m + n * m + j, (i - 1) * m + j + 1,INF);
			if(i == 1 || j == 1 || i == n || j == m) add((i - 1) * m + n * m + j, 2 * n * m + 1, INF);						//边界 
		}
	}
	S = 0;
	T = 2 * n * m + 1;
	cout << dinic();
	return 0;
}