2756: [SCOI2012]奇怪的游戏
Time Limit: 40 Sec Memory Limit: 128 MB
Description
Blinke 最近喜欢上一个奇怪的游戏。 这个游戏在一个 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\)一定具有单调性，所以我们可以二分\(x\)。
那么如何写\(check(x)\)呢？
首先我们可以将棋盘黑白染色，之后再将黑色与\(T\)相连，将白色与\(S\)相连，再将黑白色之间连接。这样就可以用一个最大流来解决。
因为每个数字都要变为\(x\)，所以可以将节点与\(S\)或\(T\)相连的边权设为\(x-val\)，之后我们可以将黑白棋子之间的边权设为\(inf\)(其实边权值可以算出，不过由于之前已经限制了边权，所以这里可以不用处理边权)。
因为这个最大流其实就是加了多少次，所以最大流应该等于所有数字与x之差之和的一半。这样，我们就可以写出\(check\)了。
另外，因为\(Cnt[0]*x - Sum[0]=Cnt[1]*x - Sum[1]\)，\(Cnt\)表示黑白棋格的个数，\(Sum\)表示黑白棋格各自的和，所以当\(Cnt[0] \neq Cnt[1]\)时，我们可以直接得出\(x\)，之后直接\(check(x)\)就好了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MS = 100000, N = 42;
const LL inl = 1LL << 55;
int ina; char inc, inb[1<<16], *ins = inb, *ine = inb; bool insign;
inline char getc() {
if (ins == ine) ine = (ins = inb) + fread(inb, 1, 1 << 16, stdin);
return (ins == ine) ? EOF : *ins++;
}
inline int geti() {
insign = false;
while ((inc = getc()) < '0' || inc > '9') insign |= inc == '-'; ina = inc - '0';
while ((inc = getc()) >= '0' && inc <= '9') ina = (ina << 3) + (ina << 1) + inc - '0';
return insign ? -ina : ina;
}
int mp[N][N], n, m;
bool col[N][N];
LL Sum[2], Num[2], mv;
namespace CC {
int To[MS], Nxt[MS], totE, head[N * N], S, T, d[N * N], dt[N * N];
LL C[MS];
inline void Adde(int a, int b, LL c) {
To[totE] = b; Nxt[totE] = head[a]; C[totE] = c; head[a] = totE++;
To[totE] = a; Nxt[totE] = head[b]; C[totE] = 0; head[b] = totE++;
}
const int dx[] = {0,0,-1,1};
const int dy[] = {1,-1,0,0};
inline int getp(const int &x, const int &y) { return (x-1)*m + y; }
LL dfs(int u, LL flow) {
if (u==T||!flow) return flow;
LL res = 0, t;
for (int i = head[u]; ~i; i = Nxt[i])
if (d[u] == d[To[i]] + 1 && C[i] > 0){
t = dfs(To[i], min(flow, C[i]));
C[i] -= t, C[i^1] += t;
res += t, flow -= t;
if (!flow) return res;
if (d[S] > T) return res;
}
if (!(--dt[d[u]])) d[S] = T + 1;
++dt[++d[u]];
return res;
}
bool check(LL x) {
memset(head, -1, sizeof head); totE = 0;
S = 0, T = getp(n, m) + 1;
LL t, tot = 0, maxflow = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
t = x - mp[i][j];
if (col[i][j]) Adde(getp(i, j), T, t);
else Adde(S, getp(i, j), t);
tot += t;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
for (int k = 0; k < 4; ++k) {
int _i = i + dx[k], _j = j + dy[k];
if (_i < 1 || _i > n || _j < 1 || _j > m) continue;
if (!col[i][j]) Adde(getp(i, j), getp(_i, _j), inl);
}
memset(d, 0, sizeof d); memset(dt, 0, sizeof dt);
dt[0] = T + 1;
while (d[S] < T + 1) maxflow += dfs(S, inl);
return tot == (maxflow << 1);
}
}
void init() {
memset(col, 0, sizeof col);
n = geti(), m = geti();
*Sum = Sum[1] = *Num = Num[1] = mv = 0LL;
bool st = true;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if ((mp[i][j] = geti()) > mv) mv = mp[i][j];
col[i][j] = !col[i][j-1];
if (j <= 1) col[i][j] = (st = !st);
++Num[col[i][j]]; Sum[col[i][j]] += mp[i][j];
}
}
#define getskip(a) (a*n*m - Sum[0] - Sum[1]) >> 1
void Work() {
if (n * m & 1) {
LL x = Sum[0] - Sum[1];
if (x >= mv && CC::check(x)) printf("%lld\n", getskip(x));
else puts("-1");
} else {
LL l = mv, r = inl / 1000, M, ans = -1;
while (l <= r) {
M = l + r >> 1;
if (CC::check(M)) r = (ans = M) - 1;
else l = M + 1;
}
if (~ans) printf("%lld\n", getskip(ans));
else puts("-1");
}
}
int main() {
for (int T = geti(); T; --T) {
init(); Work();
}
return 0;
}