标签：网络流，最大流

题目

题目传送门

Description

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

Input

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

Output

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

Sample Input

2 2

1 2

2 3

3 3

1 2 3

2 3 4

4 3 2
Sample Output

-1

HINT

【数据范围】

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

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

分析

将棋盘进行黑白点染色，设黑点个数为c1，总和为 $s1=\sum a[i][j]$

白点个数为c2，总和为 $s2=\sum a[i][j]$

设最后所有的格子内都变成x

那么列出方程

$c1*x-s1=c2*x-s2$

$x=(s1-s2)/(c1-c2)$

解出x之后可以用网络流检验答案是否可行

建图过程：

将超级源点S=0向每个黑点连边流量为x-a[i][j]，黑点和白点之间连边流量为无穷大，白点再和超级汇点连边流量为x-a[i][j]

最后看总的流量是不是 $\sum x-a[i][j]$

如果符合条件那么输出答案x，否则输出-1

但是当c1=c2时，就无法解得x，显然存在一个最小值x，满足k>=x都是一个合法的解

那么可以二分答案x（每点最终权值）然后同样用最大流dinic解决

这题调试了大半天，原因竟是数组开小，可是神奇的bzoj提醒我TLE，明明实际上是RE啊，bzoj=玄学OJ，有没有大佬知道原因的啊qwq

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define inf 1LL<<50
#define p(x,y) (x-1)*m+y
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int dx[4]={
   0,1,0,-1},dy[4]={
   1,0,-1,0};
ll s1,s2,ans;
int c1,c2,S,T,n,m,cnt,Que,last[2006],h[2006],que[2006],a[46][46];
bool col[46][46];
struct edge{
   int to,next;ll v;}e[20006];void insert(int u,int v,ll w){e[++cnt]=(edge){v,last[u],w};last[u]=cnt;e[++cnt]=(edge){u,last[v],0};last[v]=cnt;
}bool bfs()
{int head=0,tail=1,now;mem(h,-1);que[0]=S;h[S]=0;while(head<tail){now=que[head++];reg(now)if(e[i].v&&h[e[i].to]==-1){h[e[i].to]=h[now]+1;que[tail++]=e[i].to;}}return h[T]!=-1;
}inline ll dfs(int x,ll f)
{if(x==T)return f;ll w,used=0;reg(x)if(h[e[i].to]==h[x]+1){w=dfs(e[i].to,min(f-used,e[i].v));e[i].v-=w;e[i^1].v+=w;used+=w;if(used==f)return f;}if(!used)h[x]=-1;return used;
}inline ll dinic(){ll temp=0;while(bfs())temp+=dfs(S,inf);return temp;
}
bool check(ll x)
{mem(last,0);mem(e,0);cnt=1;S=0;T=n*m+1;ll tot=0;rep(i,1,n)rep(j,1,m)if(col[i][j]){insert(S,p(i,j),x-a[i][j]);tot+=x-a[i][j];rep(k,0,3){int nx=i+dx[k],ny=j+dy[k];if(nx<1||nx>n||ny<1||ny>m)continue;insert(p(i,j),p(nx,ny),inf);}}else insert(p(i,j),T,x-a[i][j]);if(dinic()==tot)return 1;else return 0;
}
int main()
{Que=read();while(Que--){int Max=0;n=read(),m=read();c1=c2=s1=s2=0;rep(i,1,n)rep(j,1,m){a[i][j]=read();col[i][j]=(i+j)&1;Max=max(Max,a[i][j]);}rep(i,1,n)rep(j,1,m)if(col[i][j])s2+=a[i][j],c2++;else s1+=a[i][j],c1++;if(c1!=c2){ll x=(s1-s2)/(c1-c2);if(x>=Max)if(check(x)){
   printf("%lld\n",(ll)x*c2-s2);continue;}puts("-1");}else{if(s1!=s2){
   puts("-1");continue;}ll l=Max,r=inf;while(l<=r){ll mid=(l+r)/2;if(check(mid))r=mid-1;else l=mid+1;}printf("%lld\n",(ll)l*c2-s2);}}return 0;
}

BZOJ2756 [SCOI2012]奇怪的游戏

题目

分析

code