奇怪的游戏[SCOI2012]

发表于 分类于 ，

题目

链接

题解

一看到棋盘，先黑白染色再说。

若棋盘中格子是奇数，则答案不满足单调性。不过此时次数可以直接解出来，或判断无解。

下面讨论格子总数为偶数的情况：

若全染成 $x$ 可以，则全染成 $x+1$ 也可以。

因此二分答案一波，看看能不能让答案为 $x$。

一次染色显然会让黑和白格子的总数都加一。

因此若白色和黑子格子里的数总数不相等，则必定无解。

新建源汇，边权为 $x-a_{i,j}$，白点黑点相邻的连边，边权为 $\infty$，表示可以同时加上很多个 $1$。

跑最大流，看是否满流即可。

程序

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
#define ll long long
#define N 1610
#define M 20000
#define inf 100000000000000000ll
inline int read()
{
	int x=0; bool f=0; char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return x;
}
namespace Dinic{
	int s,t;
	int ver[M],ne[M],head[N],tot=1,cur[N],d[N]; ll val[M];
	inline void add(int x,int y,ll z)
	{
		ver[++tot]=y; val[tot]=z; ne[tot]=head[x]; head[x]=tot;
		ver[++tot]=x; val[tot]=0; ne[tot]=head[y]; head[y]=tot;
	}
	queue<int> q;
	inline bool bfs()
	{
		for(int i=s;i<=t;i++) d[i]=0;
		for(;!q.empty();q.pop());
		for(q.push(s),d[s]=1;!q.empty();)
		{
			int u=q.front(); q.pop();
			for(int i=head[u],v;i;i=ne[i])
				if(val[i]&&!d[v=ver[i]])
				{
					d[v]=d[u]+1; q.push(v);
					if(v==t) return 1;
				}
		}
		return 0;
	}
	ll dfs(int u,ll flow)
	{
		if(u==t||!flow) return flow;
		ll res=flow,r; int v;
		for(int &i=cur[u];i&&res;i=ne[i])
			if(val[i]&&d[v=ver[i]]==d[u]+1&&(r=dfs(v,min(res,(ll)val[i]))))
				res-=r,val[i]-=r,val[i^1]+=r;
		return flow-res;
	}
	inline ll dinic()
	{
		ll flow=0;
		for(;bfs();flow+=dfs(s,inf)) for(int i=s;i<=t;i++) cur[i]=head[i];
		return flow;
	}
	inline void init() {for(int i=s;i<=t;i++) head[i]=0; tot=1;}
}
using namespace Dinic;
int n,m; ll a[44][44];
int fx[4]={1,-1,0,0};
int fy[4]={0,0,1,-1};
inline int id(int x,int y){return (x-1)*m+y;}
inline bool check(int x,int y) {return x>0&&x<=n&&y>0&&y<=m;}
inline ll build(ll tmp)
{
	ll sum=0;
	init();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if((i+j)&1) add(id(i,j),t,tmp-a[i][j]),sum+=tmp-a[i][j];
			else
			{
				add(s,id(i,j),tmp-a[i][j]);
				for(int k=0,x,y;k<4;k++)
					if(check(x=i+fx[k],y=j+fy[k]))
						add(id(i,j),id(x,y),inf);
			}
		}
	return sum;
}
inline bool check(ll x) {ll sum=build(x); return dinic()==sum;}
ll sum[2],maxx;
int main()
{
	for(int T=read();T--;)
	{
		n=read(); m=read();
		s=0; t=n*m+1;
		sum[0]=sum[1]=maxx=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				a[i][j]=read(),sum[(i+j)&1]+=a[i][j],maxx=max(maxx,a[i][j]);
		if((n*m)&1)
		{
			if(sum[0]-sum[1]<maxx) {puts("-1");continue;}
			ll num1=build(sum[0]-sum[1]);ll num2=dinic();
			printf("%lld\n",(num1==num2)?num2:-1);
		}
		else
		{
			if(sum[0]!=sum[1]) {puts("-1");continue;}
			ll l=maxx,r=maxx+maxx+1,mid;
			while(l<=r)
			{
				mid=(l+r)>>1;
				if(check(mid)) r=mid-1;
				else l=mid+1;
			}
			l=r+1;
			if(l>=maxx+maxx) {printf("-1\n"); continue;}
			build(l);
			printf("%lld\n",dinic());
		}
	}
	return 0;
}