自动搬运

查看原文

来自洛谷，原作者为

	Timmylyx 努力的小羊 咩~

搬运于2025-08-24 22:45:51，当前版本为作者最后更新于2025-07-10 22:39:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

友情提示：本题解 看起来错误，但 本蒟蒻 认为是正确的，如有不严谨欢迎各位大佬多多指出。

题意

题目说有 $N^2$ 种不同型号的木棍，木棍左右各有一个小于 $N$ 的非负整数，左侧数为 $i$，右侧数为 $j$ 的木棍有 $a_{i,j}$ 个。

现在要把它们 从左到右 拼起来，求问最多有多少对相邻的木棍使得连接他们的两个数的和为 $N$。

题解

看上去没有头绪，感觉像有源汇上下界最大费用最大流套路 而且数据范围很大，所以我们考虑 正难则反。

我们把木棍抽象成边，数抽象成点，绘制一张图。（这里就不放了）

然后我们发现这张图不太好用，因为我们没法表示和为 $N$ 的限制，所以我们考虑把边 $i\rightarrow j$ 变成 $i\rightarrow N-j$（新增点 $N$）。

下图为更改后的图：

那么我们会发现，这张图上每拿掉一条长度为 $L$ 的路径，答案会增加 $\max(L-1,0)$。

那么显然我们取完路径之后，$\sum L=\sum a$，所以我们考虑最少减几个 $1$。

我们设 $r$ 是每个点的入度，$s$ 是每个点的出度，则点 $i$ 会产生 $|r_i-s_i|$ 条“废边”（注意每条废边会被记录两次，记得除 $2$），那么我们可以考虑以这些废边为起点，假设有 $x$ 条废边，则答案减 $x$。

这是对的吗？不对！有特殊情况。假设某个连通块内没有废边，但是一条路径一定有起点，这时答案仍要减 $1$。

然后（就没有然后了）……

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 1010
int fa[N],r[N],c[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
signed main(){
	int t; cin>>t;
	while (t--){
		memset(r,0,sizeof(r));
		memset(c,0,sizeof(c));
		int n,ans=0; cin>>n;
		for (int i=0; i<=n; i++) fa[i]=i;
		for (int i=0; i<n; i++){
			for (int j=0; j<n; j++){
				int x; cin>>x; 
				if (x){
					ans+=x; r[i]+=x; c[n-j]+=x;
					if (find(i)!=find(n-j)){
						fa[find(i)]=find(n-j);
					} 
				}
			}
		}
		for (int i=0; i<=n; i++){
			if (find(i)!=i||!c[i]&&!r[i]) continue;//小心空连通块
			int sum=0,flag=0;
			for (int j=0; j<=n; j++) if (find(j)==i) sum+=abs(r[j]-c[j]);
			
			ans-=max(sum>>1,1ll);
		}
		cout<<ans<<"\n";
	}
}