bzoj 2756奇怪的游戲

2756: [SCOI2012]奇怪的游戲

Time Limit:?40 Sec??Memory Limit:?128 MB
Submit:?2571??Solved:?685
[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?

?

考慮末狀態有所有數都相等的很好性質，所以設所有數的變為x。因為每次只會對相鄰兩個格子加1，所以奇偶分治后，兩種格子的變化量相同。

所以可以列出方程

這里借用黃學長的博客

對棋盤進行黑白染色
設黑格個數為num1 數值和為sum1
設白格個數為num1 數值和為sum1

設最后都變為x
則
num1 * x – sum1 = num2 * x – sum2
x = (sum1 – sum2) / (num1 – num2)

?

然后分類討論

當num1 ≠ num2時 可以解出 x 再用網絡流check即可

對于num1 = num2時 可以發現 對于一個合法的x k>=x都是一個合法的解
因為num1 = num2 =>?(num1 + num2) % 2 == 0 可以構造一層的滿覆蓋
所以可以二分x 然后用網絡流check

建圖：
如果點k為白
建邊(s,?k, x – v[k])
如果為黑
建邊(k, t, x – v[k])
對相鄰點u、v?(u為白)
建邊 (u,?v, inf)

?

方法：利用末狀態性質，設未知數，列出方程。然后分類討論，首先要滿足方程才有解，然后可以二分答案，在check。其實如果都合法，可以直接二分末狀態，然后check。方程討論是因為解得情況在不同條件下不同。

?

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 2020
#define maxm 8020
#define INF 100000000000000lltypedef long long LL;
struct node{int next,to;LL f;
}e[maxm * 2];
int head[maxn],cnt = 1,src,sink;
int q[maxn],hh,tt,dis[maxn],cur[maxn];
int n,m,T,num1,num2,mx;
LL sum1,sum2,maxflow,x,ans;
int dt[maxn][maxn];inline void adde(int x,int y,LL c){e[++cnt].to = y;e[cnt].next = head[x];e[cnt].f = c;head[x] = cnt;e[++cnt].to = x;e[cnt].next = head[y];head[y] = cnt;
}
inline bool bfs(){tt = hh = 0;memset(dis,0,sizeof(dis));q[tt++] = src , dis[src] = 1;while ( hh < tt ){int now = q[hh++];for (int i = head[now] ; i ; i = e[i].next){if ( e[i].f && !dis[e[i].to] ){q[tt++] = e[i].to;dis[e[i].to] = dis[now] + 1;}}}return dis[sink] > 0;
}
LL dfs(int now,LL delta){if ( now == sink || !delta ) return delta;LL ret = 0;for (int &i = cur[now] ; i ; i = e[i].next){if ( e[i].f && dis[now] + 1 == dis[e[i].to] ){LL d = dfs(e[i].to,min(delta,e[i].f));ret += d , delta -= d;e[i].f -= d, e[i ^ 1].f += d;if ( !delta ) return ret;}}if ( delta ) dis[now] = -1;return ret;
} 
inline LL dinic(){LL flow = 0;while ( bfs() ){for (int i = 1 ; i <= sink ; i++) cur[i] = head[i];flow += dfs(src,INF);}return flow;
}
inline void init(LL x){memset(head,0,sizeof(head));memset(e,0,sizeof(e));cnt = 1;for (int i = 1 ; i <= n ; i++){for (int j = 1 ; j <= m ; j++){if ( (i + j) & 1 ){adde((i - 1) * m + j,sink,x - (LL)dt[i][j]);}else{int now = (i - 1) * m + j;adde(src,(i - 1) * m + j,x - (LL)dt[i][j]);if ( i > 1 ) adde(now,now - m,INF);if ( i < n ) adde(now,now + m,INF);if ( j > 1 ) adde(now,now - 1,INF);if ( j < m ) adde(now,now + 1,INF);}}}
}
int main(){freopen("input.txt","r",stdin);scanf("%d",&T);while ( T-- ){ans = sum1 = sum2 = 0 , mx = num1 = num2 = 0;scanf("%d %d",&n,&m);src = n * m + 1 , sink = n * m + 2;for (int i = 1 ; i <= n ; i++){for (int j = 1 ; j <= m ; j++){scanf("%d",&dt[i][j]);if ( (i + j) & 1 ) sum2 += (LL)dt[i][j] , num2++;else sum1 += (LL)dt[i][j], num1++;mx = max(dt[i][j],mx);}}if ( num1 != num2 ){if ( ((sum1 - sum2) % (LL)(num1 - num2)) != 0 ){printf("-1\n");continue;}	x = (sum1 - sum2) / (LL)(num1 - num2);if ( x < mx ){printf("-1\n");continue;}init(x);maxflow = dinic();if ( maxflow + sum1 == (LL)num1 * x ){printf("%lld\n",maxflow);}else printf("-1\n");}else{LL l = mx , r = INF;//二分把當前的每個數都變成mid的情況for (int i = 1 ; i <= 50 ; i++){maxflow = 0;LL mid = (l + r) >> 1;init(mid);maxflow = dinic();if ( maxflow + sum1 == (LL) num1 * mid ){ans = maxflow , r = mid;}else l = mid + 1;}if ( !ans ) printf("-1\n");else printf("%lld\n",ans);}}return 0;
}