[文章目录]
Description
这个游戏在一个 N*M 的棋盘上玩，每个格子有一个数。每次 Blinker 会选择两个相邻的格子，并使这两个数都加上 1。现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出-1。多组数据 T<=10，1<=N,M<=40 ai<=10^9
发现如果知道最后那个数(设为x)是什么的话，可以将行列构建二分图，跑残量网络，如果满流，则可行。
分类讨论:
如果n*m为偶数，如果最后相同的数大于x，都可行。可以二分答案，每次判定。
如果n*m为奇数，黑白染色，发现有一种多了一块。那么两个点集的差即为最后的x，直接判定即可。
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf=0x3bbbbbbbbbbbbbbbll;
int n,m,s,t,T;
int mp[50][50];
int head[2000],nxt[20000],to[20000],cnt;
ll f[20000];
inline int id(int i,int j)
{
if(i<1||i>n||j<1||j>m) return 0;
return (i-1)*m+j;
}
inline void add(int x,int y,ll z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
queue<int>q;
int dis[2000];
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-1,sizeof dis);
dis[s]=0; q.push(s); int x,i;
while(!q.empty())
{
x=q.front(); q.pop();
for(i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
ll dinic(int x,ll flow)
{
if(x==t) return flow;
ll xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(tmp,f[i]));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) return flow;
}
return flow-tmp;
}
bool check(ll x)
{
if(x<0) return false;
memset(head,0,sizeof head); cnt=1;
int i,j; ll ans=0;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
{
if(mp[i][j]>x) return false;
if((i+j)&1)
{
add(s,id(i,j),x-mp[i][j]); ans+=x-mp[i][j];
if(id(i-1,j)) add(id(i,j),id(i-1,j),inf);
if(id(i,j-1)) add(id(i,j),id(i,j-1),inf);
if(id(i+1,j)) add(id(i,j),id(i+1,j),inf);
if(id(i,j+1)) add(id(i,j),id(i,j+1),inf);
}
else add(id(i,j),t,x-mp[i][j]);
}
while(bfs()) ans-=dinic(s,inf);
return ans==0;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m); s=n*m+1; t=s+1;
int i,j; ll s1=0,s2=0;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
{
scanf("%d",&mp[i][j]);
if((i+j)&1) s2+=mp[i][j];
else s1+=mp[i][j];
}
if((n*m)&1)
{
if(check(s1-s2)) printf("%lld\n",(s1-s2)*(n*m/2)-s2);
else puts("-1");
}
else
{
if(s1!=s2) {puts("-1"); continue;}
ll l=0,r=0x7fffffff,mid;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
if(r==0x7fffffff) puts("-1");
else printf("%lld\n",r*(n*m/2)-s2);
}
}
return 0;
}