王者之剑

发表于 | 分类于

题目

传送门
这是在阿尔托利亚·潘德拉贡成为英灵前的事情，她正要去拔出石中剑成为亚瑟王，在这之前她要去收集一些宝石。

宝石排列在一个n×m的网格中，每个网格中有一块价值为v(i,j)的宝石，阿尔托利亚·潘德拉贡可以选择自己的起点。
开始时刻为0秒。以下操作，每秒按顺序执行
1.在第i秒开始的时候，阿尔托利亚·潘德拉贡在方格（x,y）上，她可以拿走（x，y）中的宝石。
2.在偶数秒，阿尔托利亚·潘德拉贡周围四格的宝石会消失
3.若阿尔托利亚·潘德拉贡第i秒开始时在方格（x，y）上，则在第i+1秒可以立即移动到（x+1，y），（x，y+1），（x-1，y）或（x，y-1）上，也可以停留在（x,y)上。
求阿尔托利亚·潘德拉贡最多可以获得多少价值的宝石

INPUT

第一行给出数字N,M代表行列数.N,M均小于等于100，宝石的价值不会超过10000.下面N行M列用于描述数字矩阵

OUTPUT

输出最多可以拿到多少价值宝石

SAMPLE

INPUT

2 2
1 2
2 1

OUTPUT

4

解题报告

算是基础的最小割问题。
首先，我们取值时一定是在偶数时刻，取走一个格子的值，就不能取相邻格子的值，也就是相邻格子之间的值是不相容的。
我们想，只要取得格子相容，是一定有合法路径的，有不容的点就转化到最小割上，用总值减去割掉最小的值，就是最优解。
那么我们可以黑白染色，源点与白点相连，黑点与汇点连边，不相容的点之间连边，容量INF，跑最小割即可

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e,n,w;
}a[2000001];
int pre[100001],tot;
inline void insert(int s,int e,int w){
	a[tot].e=e;
	a[tot].w=w;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int n,m;
int w[105][105],col[105][105];
inline void paint(){
	int now(1);
	for(int i=1;i<=n;i++){
		now^=1;
		for(int j=1;j<=m;j++){
			if(j&1)
				col[i][j]=now;
			else
				col[i][j]=now^1;
		}
	}
}
int S(0),T;
int ans(0),inf(0x7fffffff),sum(0);
inline void build(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(col[i][j])
				insert(S,(i-1)*m+j,w[i][j]),insert((i-1)*m+j,S,0);
			else
				insert((i-1)*m+j,T,w[i][j]),insert(T,(i-1)*m+j,0);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(col[i][j]){
				if(i!=1)
					insert((i-2)*m+j,(i-1)*m+j,0),insert((i-1)*m+j,(i-2)*m+j,inf);
				if(i!=n)
					insert(i*m+j,(i-1)*m+j,0),insert((i-1)*m+j,i*m+j,inf);
				if(j!=1)
					insert((i-1)*m+j-1,(i-1)*m+j,0),insert((i-1)*m+j,(i-1)*m+j-1,inf);
				if(j!=m)
					insert((i-1)*m+j+1,(i-1)*m+j,0),insert((i-1)*m+j,(i-1)*m+j+1,inf);
			}
		}
}
int dis[10010];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int k(q.front());
		q.pop();
		for(int i=pre[k];i!=-1;i=a[i].n){
			int e(a[i].e);
			if(!dis[e]&&a[i].w){
				dis[e]=dis[k]+1;
				q.push(e);
				if(e==t)
					return true;
			}
		}
	}
	return false;
}
inline int my_min(int a,int b){
	return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==T)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		int e(a[i].e);
		if(dis[e]==dis[now]+1&&tmp&&a[i].w){
			f=dfs(e,my_min(tmp,a[i].w));
			if(!f){
				dis[e]=0;
				continue;
			}
			a[i].w-=f;
			a[i^1].w+=f;
			tmp-=f;
		}
	}
	return flow-tmp;
} 
inline int gg(){
	freopen("Excalibur.in","r",stdin);
	freopen("Excalibur.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	n=read(),m=read();
	T=n*m+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			w[i][j]=read(),sum+=w[i][j];
	paint();
	build();
	while(bfs(S,T))
		ans+=dfs(S,inf);
	printf("%d",sum-ans);
	return 0;
}
int K(gg());
int main(){;}