BZOJ 2756: [SCOI2012]奇怪的游戏 [最大流 二分]

时间:2022-09-22 19:14:39

2756: [SCOI2012]奇怪的游戏

Time Limit: 40 Sec  Memory Limit: 128 MB
Submit: 3352  Solved: 919
[Submit][Status][Discuss]

Description

Blinker最近喜欢上一个奇怪的游戏。 
这个游戏在一个 N*M 的棋盘上玩,每个格子有一个数。每次 Blinker 会选择两个相邻
的格子,并使这两个数都加上 1。 
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同
一个数则输出-1。

Input

输入的第一行是一个整数T,表示输入数据有T轮游戏组成。 
每轮游戏的第一行有两个整数N和M, 分别代表棋盘的行数和列数。 
接下来有N行,每行 M个数。

Output

对于每个游戏输出最少能使游戏结束的次数,如果永远不能变成同一个数则输出-1。

Sample Input

2
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2

Sample Output

2
-1

HINT

【数据范围】

对于30%的数据,保证  T<=10,1<=N,M<=8

对于100%的数据,保证  T<=10,1<=N,M<=40,所有数为正整数且小于1000000000


典型的棋盘

黑白染色,黑色格子cb个,数字和为sb;白色格子cw个,数字和为sw

设最后数字为x,操作t次,每次操作一定一个黑格一个白格

cb*x=sb+t

cw*x=sw+t

解得 x=(sb-sw)/(cb-cw)

分类讨论:

1.cb!=cw 得到了x,判断合法(x>=mx)就行了

2.cb==cw (这个时候一定是n,m都是偶数)(只要有一个偶数就可以了,感谢mywaythere指出),x不确定

(1) sb!=sw 无解

(2) sb==sw 二分x是多少,找最小的合法的x

如何判断一个x合法:

黑白染色后是二分图

s--与x差值-->黑格--INF-->白格--与x差值-->t

注意:

别把m打成n别把m打成n别把m打成n别把m打成n别把m打成n别把m打成n别把m打成n别把m打成n

有好多地方啊啊啊啊啊啊啊啊啊啊啊

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=;
typedef long long ll;
const ll INF=1LL<<;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n,m,g[][],s,t;
ll cb,cw,sb,sw,x,mx;
struct edge{
int v,ne;
ll c,f;
}e[*N<<];
int cnt,h[N];
inline void ins(int u,int v,ll c){
cnt++;
e[cnt].v=v;e[cnt].c=c;e[cnt].f=;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].c=;e[cnt].f=;e[cnt].ne=h[v];h[v]=cnt;
}
int q[N],head,tail,vis[N],d[N];
bool bfs(){
memset(vis,,sizeof(vis));
memset(d,,sizeof(d));
head=tail=;
q[tail++]=s;d[s]=;vis[s]=;
while(head!=tail){
int u=q[head++];
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v;
if(!vis[v]&&e[i].c>e[i].f){
vis[v]=;
d[v]=d[u]+;
if(v==t) return true;
q[tail++]=v;
}
}
}
return false;
} int cur[N];
ll dfs(int u,ll a){
if(u==t||a==) return a;
ll flow=,f;
for(int &i=cur[u];i;i=e[i].ne){
int v=e[i].v;
if(d[v]==d[u]+&&(f=dfs(v,min(a,e[i].c-e[i].f)))>){
flow+=f;
e[i].f+=f;
e[((i-)^)+].f-=f;
a-=f;
if(a==) break;
}
}
return flow;
}
ll dinic(){
ll flow=;
while(bfs()){
for(int i=s;i<=t;i++) cur[i]=h[i];
flow+=dfs(s,INF);
}
return flow;
} inline int id(int i,int j){return (i-)*m+j;}
void build(ll x){
cnt=;memset(h,,sizeof(h));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
if((i+j)&){
ins(s,id(i,j),x-g[i][j]);
if(i->=) ins(id(i,j),id(i-,j),INF);
if(i+<=n) ins(id(i,j),id(i+,j),INF);
if(j->=) ins(id(i,j),id(i,j-),INF);
if(j+<=m) ins(id(i,j),id(i,j+),INF);
}else ins(id(i,j),t,x-g[i][j]);
}
}
bool check(ll x){
s=;t=n*m+;
build(x);
ll flow=dinic();
if(flow==x*cb-sb) return true;
else return false;
}
void solve(){
if(cb!=cw){
x=(sb-sw)/(cb-cw);
if(x>=mx&&check(x)) printf("%lld\n",cb*x-sb);
else puts("-1");
}else{
if(sb!=sw) puts("-1");
else{
ll l=mx,r=INF;
while(l<=r){
ll mid=(l+r)>>;//printf("%lld %lld %lld\n",l,r,mid);
if(check(mid)) r=mid-;
else l=mid+;
}
printf("%lld\n",cb*l-sb);
}
}
}
int main(){
int T=read();
while(T--){
n=read();m=read();
mx=cb=sb=cw=sw=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
g[i][j]=read();
mx=max(mx,(ll)g[i][j]);
if((i+j)&) cb++,sb+=g[i][j];
else cw++,sw+=g[i][j];
}
solve();
}
}