# Bzoj2756 [scoi2012]奇怪的游戏

Posted by yjjr's blog on February 6, 2018

# 题目

Description

Input

Output

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


# 分析

$c1x-s1=c2x-s2$

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

# 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;
{
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()
{
mem(h,-1);
que[0]=S;h[S]=0;
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()
{
while(Que--){
int Max=0;
c1=c2=s1=s2=0;
rep(i,1,n)
rep(j,1,m){
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;
}