自动搬运

查看原文

来自洛谷，原作者为

	longlongzhu123 **

搬运于2025-08-24 22:06:27，当前版本为作者最后更新于2018-11-23 18:09:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

二分 $\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函数

$check(x)$：

设第 $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。

代码

#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;
}