题解：P9153 「SvR-2」1+2=3（加强版）

· · 题解

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

题意

题目说有 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";
    }
}