BZOJ2756 [SCOI2012]奇怪的游戏 【网络流 + 二分】

题目

Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩，每个格子有一个数。每次 Blinker 会选择两个相邻
的格子，并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同
一个数则输出-1。

输入格式

输入的第一行是一个整数T，表示输入数据有T轮游戏组成。
每轮游戏的第一行有两个整数N和M， 分别代表棋盘的行数和列数。
接下来有N行，每行 M个数。

输出格式

对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出-1。

输入样例

2

2 2

1 2

2 3

3 3

1 2 3

2 3 4

4 3 2

输出样例

2

-1

提示

【数据范围】

对于30%的数据，保证  T<=10，1<=N,M<=8 

对于100%的数据，保证 T<=10，1<=N,M<=40，所有数为正整数且小于1000000000

题解

我们将原图黑白染色就会发现每次一定是一黑一白+1
那么我们可以分类讨论：
记黑色n1个总和s1，白色n2个总和s2
①若n1 == n2
二者s1 != s2，无论如何也不会相等
二者s1 == s2，用网络流二分检验：
S向其中一种颜色建边，容量为还差的值
同时这种颜色向周围建边，容量INF
另一种颜色向T建边，容量为还差的值
看看是否满流

②若n1 != n2
我们设x为最后的值
由黑白增量相同，可以得到等式：
$x * n1 - s1 = x * n2 - s2$
化简：
$x = \frac{s1 - s2}{n1 - n2}$
可见x为定值，若x比最大的数小，无解
否则网络流判断一下

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 45,maxm = 1000005;
const LL INF = (1ll << 50);
inline int read(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57) {
   if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();}return out * flag;
}
LL s[maxn][maxn],N,M,n1,n2,mx;
LL s1,s2,d[maxn * maxn];
int X[4] = {
   0,0,-1,1},Y[4] = {-1,1,0,0},c[maxn][maxn];
int h[maxn * maxn],ne,S,T,vis[maxn * maxn],cur[maxn * maxn];
struct EDGE{
   int to,nxt; LL f;}ed[maxm];
inline void build(int u,int v,LL w){ed[ne] = (EDGE){v,h[u],w}; h[u] = ne++;ed[ne] = (EDGE){u,h[v],0}; h[v] = ne++;
}
bool bfs(){queue<int> q; int u;for (int i = S; i <= T; i++) d[i] = INF,vis[i] = false;d[S] = 0; vis[S] = true; q.push(S);while (!q.empty()){u = q.front(); q.pop();Redge(u) if (ed[k].f && !vis[to = ed[k].to]){d[to] = d[u] + 1; vis[to] = true; q.push(to);}}return vis[T];
}
LL dfs(int u,LL minf){if (u == T || !minf) return minf;LL f,flow = 0; int to;if (cur[u] == -1) cur[u] = h[u];for (int& k = cur[u]; k; k = ed[k].nxt)if (d[to = ed[k].to] == d[u] + 1 && (f = dfs(to,min(minf,ed[k].f)))){ed[k].f -= f; ed[k ^ 1].f += f;flow += f; minf -= f;if (!minf) break;}return flow;
}
LL maxflow(){LL flow = 0;while (bfs()){fill(cur,cur + maxn * maxn,-1); flow += dfs(S,INF);}return flow;
}
bool check(LL x){S = 0; T = N * M + 1; ne = 2; memset(h,0,sizeof(h));LL tot = 0;REP(i,N) REP(j,M){if (c[i][j]){build(S,(i - 1) * M + j,x - s[i][j]),tot += x - s[i][j];for (int k = 0; k < 4; k++){int nx = i + X[k],ny = j + Y[k];if (nx < 1 || ny < 1 || nx > N || ny > M) continue;build((i - 1) * M + j,(nx - 1) * M + ny,INF);}}else build((i - 1) * M + j,T,x - s[i][j]);}return tot == maxflow();
}
void solve1(){LL x = (s1 - s2) / (n1 - n2);if (x < mx || !check(x)) puts("-1");else printf("%lld\n",x * n1 - s1);
}
void solve2(){if (s1 != s2) {
   puts("-1"); return;}LL L = mx,R = INF,mid;while (L <= R){mid = L + R >> 1;if (check(mid)) R = mid - 1;else L = mid + 1;}printf("%lld\n",(LL)L * n1 - s1);
}
int main(){int Tim = read();while (Tim--){N = read(); M = read(); n1 = n2 = s1 = s2 = 0; mx = 0;REP(i,N) REP(j,M) c[i][j] = (i + j ) & 1,s[i][j] = read();REP(i,N) REP(j,M){if (c[i][j]) n1++,s1 += s[i][j];else n2++,s2 += s[i][j];mx = max(mx,s[i][j]);}if (n1 != n2) solve1();else solve2();}return 0;
}