這個題的數據，太卡了，TLE了兩晚上，各種調試優化，各種蛋疼。

2756: [SCOI2012]奇怪的游戲
Time Limit: 40 Sec Memory Limit: 128 MB
Submit: 2311 Solved: 598
[Submit][Status][Discuss]

Description
Blinker最近喜歡上一個奇怪的游戲。
這個游戲在一個 N*M 的棋盤上玩，每個格子有一個數。每次 Blinker 會選擇兩個相鄰
的格子，并使這兩個數都加上 1。
現在 Blinker 想知道最少多少次能使棋盤上的數都變成同一個數，如果永遠不能變成同
一個數則輸出-1。

Input
輸入的第一行是一個整數T，表示輸入數據有T輪游戲組成。
每輪游戲的第一行有兩個整數N和M， 分別代表棋盤的行數和列數。
接下來有N行，每行 M個數。

Output
對于每個游戲輸出最少能使游戲結束的次數，如果永遠不能變成同一個數則輸出-1。

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
對于100%的數據，保證 T<=10，1<=N,M<=40，所有數為正整數且小于1000000000

Source

這道題一看到，還真沒直接想到網絡流，看了看每次必須找相鄰兩個點，偶然想到國際象棋，于是黑白染色；
于是統計出wnum，bnum，wsum，bsum（染成White的格子數，和初始的總數，及染成Black的格子數和初始總數）
二分最后的結果X（x為滿足所有格子都一樣時的格子中的數），所以可以得到下面的一個關系式：

X * wnum - wsum = X * bnum - bsum==> X * bnum - X * wnum = bsum - wsum==> X = （bsum - wsum）/（bnum - wnum）

每次相鄰兩個+1可知，每次必然滿足wsum+1，bsum+1；
所以我們得到 當 bnum==wnum 時，如果滿足bsum！=wsum 則無解
當 bsum==wsum 時，如果x成立，則任何>=x的數都成立，所以二分X即可
當 bnum！=wnum 時，發現至多有一個解，所以解得X，判斷是否符合即可

建圖：
超級源S向每個白點連邊，邊權為X-white【i】；
每個白點向相鄰的黑點連邊，邊權為INF；
每個黑點向超級匯T連邊，邊權為X-black【i】；
（X為二分出的值，white【】，black【】表示初始值）
用tot記錄差值，判斷最大流是否滿足即可

值得注意的是這個題的 時間限制，以及long long。

code：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxl (1LL<<50) #define zb(x,y) (x-1)*m+y int dis[2005]; struct data{int next,to;long long v; }edge[10005]; int cnt=1,head[2005]={0}; int q[2005],h,t; int jz[50][50]={0}; int cur[2005]; int n,m,tim; int wnum,bnum; long long wsum,bsum; int num; int mx=0; long long tot=0; bool zt[50][50]; int move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};void add(int u,int v,long long w) {cnt++;edge[cnt].next=head[u];head[u]=cnt;edge[cnt].to=v;edge[cnt].v=w; }void insert(int u,int v,long long w) {add(u,v,w);add(v,u,0); }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; }void init() { n=read(); m=read();for (int i=1; i<=n; i++)for (int j=1; j<=m; j++){jz[i][j]=read();zt[i][j]=(i+j)&1;mx=max(mx,jz[i][j]);}num=n*m+1;for (int i=1; i<=n; i++)for (int j=1; j<=m; j++)if (zt[i][j]) {wnum++;wsum+=jz[i][j];}else {bnum++;bsum+=jz[i][j];} }void make(long long mv) {cnt=1;memset(head,0,sizeof(head));for (int i=1; i<=n; i++)for (int j=1; j<=m; j++)if (zt[i][j]) {insert(0,zb(i,j),mv-jz[i][j]);tot+=mv-jz[i][j];for (int k=0; k<4; k++){int x=i+move[k][0],y=j+move[k][1];if (x>0 && x<=n && y>0 && y<=m)insert(zb(i,j),zb(x,y),maxl);}}else insert(zb(i,j),num,mv-jz[i][j]); }bool bfs() {memset(dis,-1,sizeof(dis));q[1]=0; dis[0]=1;h=0;t=1;while (h<t) {int j=q[++h],i=head[j];while (i){if (edge[i].v>0 && dis[edge[i].to]<0){dis[edge[i].to]=dis[j]+1;q[++t]=edge[i].to;}i=edge[i].next;}}if (dis[num]>0)return true;elsereturn false; }long long dfs(int loc,long long low) {if(loc==num)return low;long long flow,cost=0;for(int i=cur[loc];i;i=edge[i].next)if(dis[edge[i].to]==dis[loc]+1){flow=dfs(edge[i].to,min(low-cost,edge[i].v));edge[i].v-=flow;edge[i^1].v+=flow;if(edge[i].v) cur[loc]=i;cost+=flow;if(cost==low)return low;}if(!cost)dis[loc]=-1;return cost; }long long dinic() {long long temp=0;while (bfs()){for (int i=0; i<=num; i++) cur[i]=head[i];temp+=dfs(0,maxl);}return temp; }bool check(long long ans) {tot=0;make(ans);long long temp=dinic();if (temp==tot) return 1;return 0; }int main() {tim=read();while (tim--){wnum=bnum=0;wsum=bsum=0;mx=0;init();if (wnum==bnum){if (wsum!=bsum) {puts("-1");continue;}long long left=mx;long long right=maxl;while (left<=right){long long mid=(left+right)/2;if (check(mid)) right=mid-1;else left=mid+1;}printf("%lld\n",left*wnum-wsum);}else{long long x=(bsum-wsum)/(bnum-wnum);if (x>=mx) {if (check(x)) {printf("%lld\n",(x*wnum)-wsum);continue;}else puts("-1");}else puts("-1"); }}return 0; }

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5346227.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的BZOJ-2756 奇怪的游戏 黑白染色+最大流+当前弧优化+二分判断+分类讨论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。