题解 P5038 【[SCOI2012]奇怪的游戏】
longlongzhu123
·
·
题解
二分 \times 网络流
一开始看到题目脑子一片空白。。。QAQ
仔细观察题目：
选择两个相邻的格子
黑白染色！QwQ
并使这两个数都加上1
二分图！QwQ
棋盘上的数都变成同一个数
最大流！QwQ
最少多少次
二分！QwQ
好了这题解法已经很明朗了。。。（诶诶你刚刚说了什么来着？）
具体来说
因为这题是二维棋盘，考虑黑白染色，建立二分图。
设黑点的个数有 B 个，权值总和为 b ，白点的个数有 W 个，权值总和为 w 。
对于每次操作，因为是选择相邻的两个节点，所以黑点白点肯定各有一个被操作，即 b 和 w 各加一。
设最后全部数字都变成 X ，那么就会有有 B \times X - b = W \times X - w （等于操作的次数）。
稍微化简一下： (B - W) \times X = b - w ， X = (b - w) \div (B - W) 。
这条等式成立的条件是 B \ne W ，（小学奥数：除数不能为0）
B \ne W
如果 B \ne W ，我们可以直接求出 X 。
然而，我们直接求出的X不一定是可行的，需要使用check判定它是否可行（见后）。
B = W
如果 B = W ，就意味着 N 、 M 中有一个是偶数（很明显好吧qwq）。
在 B=W 的情况下，如果一个 X 可行，那么我们可以铺满整个棋盘，使整个棋盘的所有数都加上一，即 X+1 也可行。
同理，当 X 不可行时， X-1 也肯定不可行。
我们可以二分出 X ，同样使用check判定。
注意：我们每次 b 和 w 各加一，而且 B = W ，最后所有数都变成 X ，因此若一开始的 b 不等于 w ，我们不管怎么操作，都不能求出一个合法的解。
check函数
设第 $i$ 个点的值为 $v[i]$ ，
网络流建图，将 $S$ 向所有黑点 $i$ 连边，容量为 $x - v[i]$ ，意味着需要对这个点操作 $x - v[i]$ 次。
将所有黑点 $i$ 向其相邻的白点 $j$ 连边，容量为 $INF$ 。
将所有白点 $j$ 向 $T$ 连边，容量为 $x - v[j]$ ，意味着这个点最多接受 $x - v[j]$ 次来自黑点的操作。
设所有 $x - v[i]$ 的和为 $V$ ，
在图上运行最大流，判断最大流是否等于 $V$ 即可。
若最大流等于 $V$ ，那么意味着图上所有边都流满，即 $x$ 可行，返回`true`。
否则返回`false`。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int INF;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
struct Graph{
static const int MAXM=200000+10;
static const int MAXN=10000+10;
struct Edge{
int from,to,cap;
int next;
}node[MAXM];
int head[MAXN],top;
void init(){
top=1;
memset(head, 0, sizeof(head));
s = MAXN - 1;
t = MAXN - 2;
}
void add(int u,int v,int cap){
top++;
node[top].next=head[u];
node[top].from=u;
node[top].to=v;
node[top].cap=cap;
head[u]=top;
top++;
node[top].next=head[v];
node[top].from=v;
node[top].to=u;
node[top].cap=0;
head[v]=top;
}
int s,t;
int dis[MAXN];
queue<int> Q;
bool bfs(){
memset(dis,-1,sizeof(dis));
Q.push(s);
dis[s]=0;
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(int i=head[u];i;i=node[i].next){
int v=node[i].to;
if(dis[v]==-1&&node[i].cap){
dis[v]=dis[u]+1;
Q.push(v);
}
}
}
return dis[t]!=-1;
}
int dfs(int u,int flow){
if(u==t)
return flow;
else{
int ret=flow;
for(int i=head[u];i&&ret;i=node[i].next){
int v=node[i].to;
if(dis[v]==dis[u]+1&&node[i].cap){
int k=dfs(v,min(ret,node[i].cap));
node[i].cap-=k;
node[i^1].cap+=k;
ret-=k;
}
}
if(ret == flow)
dis[u] = -1;
return flow-ret;
}
}
int dinic(){
int ans=0;
while(bfs())
ans+=dfs(s,INF);
return ans;
}
}G;
#define POINT(X, Y) ((X) * 40 + (Y))
int T, n, m;
int a[100][100];
bool check(int val) {
G.init();
int sum = 0;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
if((i + j) % 2 == 0) { // X
G.add(G.s, POINT(i, j), val - a[i][j]);
sum += val - a[i][j];
for(int k = 0; k < 4; k ++) {
int tx = i + dx[k];
int ty = j + dy[k];
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m) {
G.add(POINT(i, j), POINT(tx, ty), INF);
}
}
}
else { // Y
G.add(POINT(i, j), G.t, val - a[i][j]);
}
}
}
return G.dinic() == sum;
}
signed main() {
INF = 0x7F7F7F7F7F7F7F7F;
cin>>T;
while(T --) {
cin>>n>>m;
int max1 = 0;
int s0, s1, c0, c1;
s0 = s1 = c0 = c1 = 0;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
cin>>a[i][j];
max1 = max(max1, a[i][j]);
if((i + j) % 2 == 0) {
s0 += a[i][j];
c0 ++;
}
else {
s1 += a[i][j];
c1 ++;
}
}
}
if(c0 != c1) {
int x = (s0 - s1) / (c0 - c1); // c0 > c1
if(x >= max1 && check(x)) {
cout<<x * c1 - s1<<endl;
}
else {
cout<<-1<<endl;
}
}
else {
if(s0 != s1) {
cout<<-1<<endl;
}
else {
int top = INF >> 1, end = max1 - 1;
while(end + 1 != top) {
int mid = (top + end) >> 1;
if(check(mid)) { // >= mid is OK
top = mid;
}
else {
end = mid;
}
}
if(top == INF >> 1) {
cout<<-1<<endl;
}
else {
cout<<top * c1 - s1<<endl;
}
}
}
}
return 0;
}
```