2756: [SCOI2012]奇怪的游戏
Time Limit: 40 Sec Memory Limit: 128 MBSubmit: 2925 Solved: 792
[Submit][Status][Discuss]
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
Source
Solution
一道比较有趣的题目
先对题目进行分析：
首先我们考虑对棋盘黑白染色，那么我们发现：“每次相邻两个+1”，显然是一黑一白+1
那么我们先统计出WhiteNum，BlackNum（黑白点的数目），WhiteSum，BlackSum（黑白点初始权值和）
那么对于一次增加，显然是WhiteSum+1,BlackSum+1
考虑对最后的情况进行讨论：
那么很显然，当WhiteNum==BlackNum时（即总点数为偶数）
如果WhiteSum！=BlackSum，显然无解
如果WhiteSum==BlackSum时，我们发现，对于X如果成立，那么X+1一定成立，显然满足二分的性质，那么二分这个值，进行判定
当WhiteNum!=BlackNum时（即总点数为奇数）
发现显然，若有解，则解唯一，那么直接验证正确性即可
至于解怎么求？
那么假设我们知道最后值为X，那么显然可以得到$X*WhiteNum-WhiteSum=X*BlackNum-BlackSum$
移项后显然可以化减出$X=frac{BlackSum-WhiteSum}{BlackNum-WhiteNum}$
那么考虑建图：
S-->白点，约束为X-val[i][j]
黑点-->T，约束为X-val[i][j]
相邻的白点-->黑点，约束为INF
判断是否满流即可
Code
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; 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; } #define MAXM 1001000 #define MAXN 2010 int Cas,N,M,Mat[50][50]; struct EdgeNode{int next,to;long long cap;}edge[MAXM]; int head[MAXN],cnt=1; void AddEdge(int u,int v,long long w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].cap=w;} void InsertEdge(int u,int v,long long w) {AddEdge(u,v,w); AddEdge(v,u,0);} long long dis[MAXN];int que[MAXN<<1],cur[MAXN],S,T; bool bfs() { for (int i=S; i<=T; i++) dis[i]=-1; que[0]=S; dis[S]=0; int he=0,ta=1; while (he<ta) { int now=que[he++]; for (int i=head[now]; i; i=edge[i].next) if (edge[i].cap && dis[edge[i].to]==-1) dis[edge[i].to]=dis[now]+1,que[ta++]=edge[i].to; } return dis[T]!=-1; } long long dfs(int loc,long long low) { if (loc==T) return low; long long w,used=0; for (int i=cur[loc]; i; i=edge[i].next) if (edge[i].cap && dis[edge[i].to]==dis[loc]+1) { w=dfs(edge[i].to,min(low-used,edge[i].cap)); edge[i].cap-=w; edge[i^1].cap+=w; used+=w; if (edge[i].cap) cur[loc]=i; if (used==low) return low; } if (!used) dis[loc]=-1; return used; } #define INF 1LL<<60 long long dinic() { long long tmp=0; while (bfs()) { for (int i=S; i<=T; i++) cur[i]=head[i]; tmp+=dfs(S,INF); } return tmp; } void init() {cnt=1; memset(head,0,sizeof(head));} int col[50][50],id[50][50],ID; bool OK(int x,int y) {return (x>=1 && x<=N) && (y>=1 && y<=M);} bool Check(long long X) { long long Tot=0; init(); for (int i=1; i<=N; i++) for (int j=1; j<=M; j++) if (col[i][j]) { InsertEdge(S,id[i][j],X-Mat[i][j]); Tot+=X-Mat[i][j]; if (OK(i-1,j)) InsertEdge(id[i][j],id[i-1][j],INF); if (OK(i+1,j)) InsertEdge(id[i][j],id[i+1][j],INF); if (OK(i,j-1)) InsertEdge(id[i][j],id[i][j-1],INF); if (OK(i,j+1)) InsertEdge(id[i][j],id[i][j+1],INF); } else InsertEdge(id[i][j],T,X-Mat[i][j]); long long MaxFlow=dinic(); return Tot==MaxFlow; } long long Wn,Ws,Bn,Bs; void BuildGraph() { S=0; T=N*M+1; Wn=Bn=Ws=Bs=0; ID=0; int maxx=0; for (int i=1; i<=N; i++) for (int j=1; j<=M; j++) col[i][j]=(i+j)&1,id[i][j]=++ID,maxx=max(maxx,Mat[i][j]); for (int i=1; i<=N; i++) for (int j=1; j<=M; j++) if (col[i][j]) Wn++,Ws+=Mat[i][j]; else Bn++,Bs+=Mat[i][j]; if (Wn==Bn && Ws!=Bs) {puts("-1"); return;} if (Wn==Bn) { long long l=maxx,r=(1LL<<50); while (l<=r) { long long mid=(l+r)>>1; if (Check(mid)) r=mid-1; else l=mid+1; } printf("%lld ",l*Wn-Ws); } else { long long X=(Bs-Ws)/(Bn-Wn); if (X<maxx) {puts("-1"); return;} if (Check(X)) printf("%lld ",X*Wn-Ws); else puts("-1"); } } int main() { Cas=read(); while (Cas--) { N=read(),M=read(); for (int i=1; i<=N; i++) for (int j=1; j<=M; j++) Mat[i][j]=read(); BuildGraph(); } return 0; }
初学网络流时做的.....当时小号好像WA，TLE的非常惨.....然后大号居然一直忘交了......
然而我但是傻傻的只会单路增广，还幼稚的说BZOJ有毒，正解TLE.....