首页 > 代码库 > BZOJ 2756 奇怪的游戏（最大流）
BZOJ 2756 奇怪的游戏（最大流）
题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2756
题意：在一个 N*M 的棋盘上玩，每个格子有一个数。每次 选择两个相邻的格子，并使这两个数都加上 1。 问最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出-1。
思路：对棋盘进行黑白染色，则每次操作使得黑白两色的格子总和各增加1。设黑色总和s1,个数cnt1；白色总和s2,个数cnt2，设最后的数字为x，那么有：
x*cnt1-s1=x*cnt2-s2。
（1）若cnt1！=cnt2，那么x是唯一的，x=(s1-s2)/(cnt1-cnt2)，只要判定这个x是否合法即可；
（2）若cnt1=cnt2，那么x是不唯一的，但是x是单调的，即若x可以，则x+1也可以，因为黑白可以两两配对后各增加1。因此可以二分x，判定是否可行。
现在就是给定x判定是否可行。原点向黑格子连边，白格子向汇点连边，权值都是x-格子的数字。相邻格子连边无穷。满流即可。
struct node{ int v,next; i64 cap;};node edges[N];int head[N],e;void add(int u,int v,i64 cap){ edges[e].v=v; edges[e].cap=cap; edges[e].next=head[u]; head[u]=e++;}void Add(int u,int v,i64 cap){ add(u,v,cap); add(v,u,0);}int pre[N],h[N],num[N],cur[N];i64 Maxflow(int s,int t,int n){ int i; for(i=0;i<=n;i++) h[i]=num[i]=0,cur[i]=head[i]; int u=s,v,x; i64 ans=0,Min; while(h[u]<n) { if(u==t) { Min=inf+1; for(i=s;i!=t;i=edges[cur[i]].v) { x=cur[i]; if(edges[x].cap<Min) Min=edges[x].cap,v=i; } ans+=Min; u=v; for(i=s;i!=t;i=edges[cur[i]].v) { x=cur[i]; edges[x].cap-=Min; edges[x^1].cap+=Min; } } for(i=cur[u];i!=-1;i=edges[i].next) { v=edges[i].v; if(edges[i].cap>0&&h[u]==h[v]+1) break; } if(i!=-1) { cur[u]=i; pre[edges[i].v]=u; u=edges[i].v; } else { if(--num[h[u]]==0) break; cur[u]=head[u]; x=n; for(i=head[u];i!=-1;i=edges[i].next) { if(edges[i].cap>0) x=min(x,h[edges[i].v]); } h[u]=x+1; num[x+1]++; if(u!=s) u=pre[u]; } } return ans;}i64 a[55][55];int n,m,b[55][55],s,t;int dx[]={0,0,1,-1};int dy[]={1,-1,0,0};int check(i64 p){ clr(head,-1); e=0; s=0; t=n*m+1; int i,j,k,x,y; i64 sum=0; FOR1(i,n) FOR1(j,m) { if(p<a[i][j]) return 0; if((i+j)&1) Add(s,b[i][j],p-a[i][j]),sum+=p-a[i][j]; else Add(b[i][j],t,p-a[i][j]); if((i+j)%2==0) continue; FOR0(k,4) { x=i+dx[k]; y=j+dy[k]; if(x>=1&&x<=n&&y>=1&&y<=m) { Add(b[i][j],b[x][y],inf); } } } return Maxflow(s,t,t+1)==sum;}i64 cal(){ i64 s1=0,s2=0,cnt1=0,cnt2=0,Max=0,ans; int i,j,k=0; FOR1(i,n) FOR1(j,m) b[i][j]=++k; FOR1(i,n) FOR1(j,m) { upMax(Max,a[i][j]); if((i+j)%2==0) s1+=a[i][j],cnt1++; else s2+=a[i][j],cnt2++; } if(cnt1!=cnt2) { ans=(s1-s2)/(cnt1-cnt2); if(check(ans)) return ans*cnt1-s1; return -1; } if(s1!=s2) return -1; i64 low=Max,high=inf,mid; ans=-1; while(low<=high) { mid=(low+high)>>1; if(check(mid)) ans=mid,high=mid-1; else low=mid+1; } if(ans==-1) return -1; return ans*cnt1-s1;}int main(){ rush() { RD(n,m); int i,j; FOR1(i,n) FOR1(j,m) RD(a[i][j]); PR(cal()); }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。