2756: [SCOI2012]奇怪的游戏
题目：传送门
题解：
发现做不出来的大难题一点一个网络流
%大佬
首先黑白染色（原来是套路...）染色之后就可以保证每次操作都一定会使黑白各一个各自的值加1
那么我们接着统计一下黑白格子个数cnt1和cnt2，以及各自的权值和sum1和sum2
然后就要分情况讨论了：
1、在cnt1不等于cnt2的情况下
假设有解且最终的数值均为ans，那么不难发现：cnt1*ans-cnt2*ans=sum1-sum2(因为每次操作黑白格子的总和同时加1，所以总和差始终不变)
那就可以直接推导出ans=(sum1-sum2)/(cnt1-cnt2) 那么我们其实就只需要判断一下该值是否合法就OK
2、cnt1=cnt2
若sum1不等于sum2 那么一定输出-1，因为差不变啊，显然（不过好像没有这种点）
若sum1=sum2，那么设最终的数值为ans
如果ans满足答案，那么ans+1也一定满足，显然存在单调性，直接就二分check
判断ans是否合法：st连白点，流量ans-d[i][j]；黑点连ed，流量ans-d[i][j]；相邻的不同颜色的点相连，流量无限；那么只要看看是否满流就好啊。。。
注意上界有点大...
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define inf 999999999999999999
using namespace std;
typedef long long LL;
struct node
{
int x,y,next,other;LL c;
}a[];int len,last[];
void ins(int x,int y,LL c)
{
LL k1,k2;
k1=++len;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len; k2=++len;
a[len].x=y;a[len].y=x;a[len].c=;
a[len].next=last[y];last[y]=len; a[k1].other=k2;
a[k2].other=k1;
}
int list[],h[],st,ed,head,tail;
bool bt_h()
{
memset(h,,sizeof(h));h[st]=;
list[]=st;head=;tail=;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]== && a[k].c>)
{
h[y]=h[x]+;
list[tail++]=y;
}
}
head++;
}
if(h[ed]>)return true;
return false;
}
LL find_flow(int x,LL flow)
{
if(x==ed)return flow;
LL s=,t;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]==h[x]+ && a[k].c> && s<flow)
{
s+=t=find_flow(y,min(a[k].c,flow-s));
a[k].c-=t;a[a[k].other].c+=t;if(s==flow)break;
}
}
if(s==)h[x]=;
return s;
}
int T;
int n,m;
LL mp[][];int d[][];
bool f[][];//黑false白true染色
const int dx[]={,-,,,};
const int dy[]={,,,-,};
bool check(LL sum)
{
LL ret=;
len=;memset(last,,sizeof(last));st=n*m+,ed=st+;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(f[i][j]==true)ins(st,d[i][j],sum-mp[i][j]),ret+=sum-mp[i][j];
else ins(d[i][j],ed,sum-mp[i][j]);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)if(f[i][j]==true)
for(int k=;k<=;k++)
{
int tx=i+dx[k],ty=j+dy[k];
if(d[tx][ty]!=- && f[i][j]!=f[tx][ty])ins(d[i][j],d[tx][ty],inf);
}
LL ans=;while(bt_h())ans+=find_flow(st,inf);
return ret==ans?true:false;
}
LL sol(LL sum)
{
LL ans=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
ans+=(sum-mp[i][j]);
return ans/2LL;
}
int main()
{
scanf("%d",&T);while(T--)
{
LL cnt1=,cnt2=,sum1=,sum2=,maxx=;
scanf("%d%d",&n,&m);memset(mp,,sizeof(mp));memset(d,-,sizeof(d));memset(f,true,sizeof(f));
int ss=;for(int i=;i<=n;i++)for(int j=;j<=m;j++)d[i][j]=++ss;
for(int i=;i<=n;i++)for(int j=;j<=m;j++)scanf("%lld",&mp[i][j]),sum1+=mp[i][j],maxx=max(maxx,mp[i][j]);
for(int i=;i<=n;i++)
for(int j=i%+;j<=m;j+=)
f[i][j]=false,cnt2++,sum2+=mp[i][j];
sum1-=sum2;cnt1=n*m-cnt2;
if(cnt1==cnt2)
{
if(sum1!=sum2)printf("-1\n");
else
{
LL l=maxx,r=inf,ans=-;
while(l<=r)
{
LL mid=(l+r)/;
//if(mid<maxx)l=mid+1;
if(check(mid))r=mid-,ans=mid;
else l=mid+;
}
if(ans==-)printf("-1\n");
else printf("%lld\n",sol(ans));
}
}
else
{
LL ans=(sum1-sum2)/(cnt1-cnt2);
if(ans<maxx || check(ans)==false)printf("-1\n");
else printf("%lld\n",sol(ans));
}
}
return ;
}