题目描述
BlinkerBlinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N \times MN×M 的棋盘上玩，每个格子有一个数。每次BlinkerBlinker会选择两个相邻的格子，并使这两个数都加上11。
现在BlinkerBlinker想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出-1−1。
输入格式
输入的第一行是一个整数TT，表示输入数据有T轮游戏组成。
每轮游戏的第一行有两个整数NN和MM， 分别代表棋盘的行数和列数。 接下来有NN行，每行MM个数。
输出格式
对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出-1−1。
输入输出样例
输入 #1复制
2
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2
输出 #1复制
2
-1
说明/提示
对于30%的数据，保证T<=10,1<=N,M<=8T<=10,1<=N,M<=8
对于100%的数据，保证 T<=10,1<=N,M<=40T<=10,1<=N,M<=40，所有数为正整数且小于10000000001000000000
不愧是一道黑题，还是挺难的。
看到这道题，我们看到让相邻两个增加，我们是不是可以想到这是一张二分图。然后就可以黑白染色了，然后设当前的最小值为x，白色的个数为nw，总和为sw，黑色的个数为nb，总和为sb。
然后就有如下等式：nw * x - sw = nb * x - sb ，我们就能解出 x = (sw-sb) / (nw-nb)
因为我们每次必然是黑色，白色个数各加1，所以如果个数相等，并且总和不等时，必然无解。
如果个数不相等，那么x必然唯一。
所以我们要做的事情就是，判断当前的值都为x时，是否合法。
我们二分x，因为个数相等时，肯定具有二分性。
如果当前的x，我们建图：s连向白点，然后流量就为 x-g[i][j] ，代表流出去的流量，也就是需要增加的值，然后向四边连流量为inf的边，代表可以选择任意一个一起增加值。黑点向T连边，代表需要增加的值，流量为x-g[i][j] 。最后判断最大流是不是需要增加的总和即可。
AC代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int N=10010,M=4e5+10;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int T,n,m,g[45][45],h[N],sw,sb,nb,nw,l,r,s,t;
int head[N],nex[M],to[M],w[M],tot;
inline void ade(int a,int b,int c){
to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c){ade(a,b,c); ade(b,a,0);}
inline int id(int x,int y){return (x-1)*m+y;}
inline int bfs(){
queue<int> q; q.push(s); memset(h,0,sizeof h); h[s]=1;
while(q.size()){
int u=q.front(); q.pop();
for(int i=head[u];i;i=nex[i]){
if(w[i]&&!h[to[i]]){
h[to[i]]=h[u]+1; q.push(to[i]);
}
}
}
return h[t];
}
int dfs(int x,int f){
if(x==t) return f; int fl=0;
for(int i=head[x];i&&f;i=nex[i]){
if(w[i]&&h[to[i]]==h[x]+1){
int mi=dfs(to[i],min(w[i],f));
w[i]-=mi; w[i^1]+=mi; fl+=mi; f-=mi;
}
}
if(!fl) h[x]=-1;
return fl;
}
inline int dinic(){
int res=0;
while(bfs()) res+=dfs(s,inf);
return res;
}
inline int check(int mid){
tot=1; memset(head,0,sizeof head); int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if((i+j)&1){
add(s,id(i,j),mid-g[i][j]);
for(int k=0;k<4;k++){
int tx=i+dx[k],ty=j+dy[k];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m) add(id(i,j),id(tx,ty),inf);
}
}else add(id(i,j),t,mid-g[i][j]),res+=mid-g[i][j];
}
}
return dinic()==res;
}
signed main(){
cin>>T;
while(T--){
cin>>n>>m; l=0; t=n*m+1; sb=sw=nb=nw=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j]; l=max(l,g[i][j]);
if((i+j)&1) sb+=g[i][j],nb++;
else sw+=g[i][j],nw++;
}
}
if((n*m)&1){
int p=(sw-sb)/(nw-nb);
if((sw-sb)%(nw-nb)==0&&p>=l&&check(p)) cout<<p*nb-sb<<endl;
else puts("-1"); continue;
}
if(sw!=sb){puts("-1"); continue;}
r=inf>>1;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
if(r!=inf>>1) cout<<nb*l-sb<<endl;
else puts("-1");
}
return 0;
}
京公网安备 11010502036488号