Codeforces Round 1083 (Div. 2)——CF-2205-F. Simons and Reconstructing His Roads（遇到一道题目没有思路，可以先降低约束试一试）（+-+-，需要想到差分）（对割的理解以及使用）（格林公式的应用）

题目大意

题目大意

给定一个 $n \times m$ 的网格图，包含交汇点 $(1,1)$ 到 $(n,m)$。网格中的相邻交汇点之间存在道路：

• 点 $(i,j)$ 与 $(i+1,j)$ 之间为垂直道路，其权值为 $w_{i,j}$。

• 点 $(i,j)$ 与 $(i,j+1)$ 之间为水平道路，其权值为 $v_{i,j}$。

由于一些事故，部分道路无法被重建（由输入状态 $0$ 表示），其余道路可选择是否重建（由输入状态 $1$ 表示）。

对于网格中的任意一个交汇点，如果与其相连且最终被重建的道路数量为偶数，则称该交汇点是“优雅的”。
如果所有的交汇点都是“优雅的”，则称当前的整个道路重建方案是“完美的”。

美丽值计算方式

对于一个“完美的”重建方案，其“美丽值”的计算方式如下：

1. 初始美丽值为 $0$。

2. 对于每一行 $i$ ($1 \le i \le n-1$)，找出所有在这一行向下延伸（即连接 $(i,j)$ 与 $(i+1,j)$）且被重建的垂直道路。设它们所在的列号从小到大依次为 $c_1 < c_2 < c_3 < \dots$，则将 $w_{i,c_1} - w_{i,c_2} + w_{i,c_3} - w_{i,c_4} + \dots$ 累加到美丽值中。

3. 对于每一列 $j$ ($1 \le j \le m-1$)，找出所有在这一列向右延伸（即连接 $(i,j)$ 与 $(i,j+1)$）且被重建的水平道路。设它们所在的行号从小到大依次为 $r_1 < r_2 < r_3 < \dots$，则将 $v_{r_1,j} - v_{r_2,j} + v_{r_3,j} - v_{r_4,j} + \dots$ 累加到美丽值中。
   （简单来说，就是分别对“每行向下的重建道路”和“每列向右的重建道路”按坐标顺序交替加减其权值）

目标：在所有“完美的”重建方案中，求出最大的“美丽值”。

输入格式

• 第一行包含测试用例数 $t$ ($1 \le t \le 5 \cdot 10^4$)。

• 每个测试用例的第一行包含 $n$ 和 $m$ ($2 \le n, m \le 2 \cdot 10^5, \sum n \cdot m \le 4 \cdot 10^5$)。

• 接下来 $n-1$ 行，每行 $m$ 个整数，表示垂直道路的权值 $w_{i,j}$。

• 接下来 $n$ 行，每行 $m-1$ 个整数，表示水平道路的权值 $v_{i,j}$。

• 接下来 $n-1$ 行，每行一个长度为 $m$ 的 01 字符串，表示各条垂直道路是否可以被重建。

• 接下来 $n$ 行，每行一个长度为 $m-1$ 的 01 字符串，表示各条水平道路是否可以被重建。

输出格式

对于每个测试用例，输出一个整数，表示在所有完美重建方案中能获得的最大美丽值。

样例数据

4
3 4
2 3 -2 3
4 9 4 -4
3 4 -2
-9 -5 1
6 -1 -3
1111
1111
111
111
111
2 4
4 23 1 35
6 12 -17
-14 1 -40
0100
000
101
3 3
1 0 1
0 1 0
1 0
0 1
0 0
110
111
10
11
11
3 4
13 7 6 -12
3 -5 12 -6
-3 10 -15
-5 8 -11
10 0 -5
1111
0110
110
101
010

样例解释

以第一个测试用例为例（$n=3, m=4$，且所有道路均允许重建），在使得所有交汇点相连重建道路数均为偶数的前提下，取得最大美丽值的方案如下：

垂直道路（向下的边）的选择：

• 第 1 行向下重建位于列 1、列 3 的道路，权值分别为 $2, -2$，贡献值为：$2 - (-2)$

• 第 2 行向下重建位于列 2、列 4 的道路，权值分别为 $9, -4$，贡献值为：$9 - (-4)$

水平道路（向右的边）的选择：

• 第 1 列向右重建位于行 1、行 2 的道路，权值分别为 $3, -9$，贡献值为：$3 - (-9)$

• 第 2 列向右重建位于行 1、行 3 的道路，权值分别为 $4, -1$，贡献值为：$4 - (-1)$

• 第 3 列向右重建位于行 2、行 3 的道路，权值分别为 $1, -3$，贡献值为：$1 - (-3)$

该方案不仅满足所有交汇点度数皆为偶数，且其总美丽值为：
$(2 - (-2)) + (9 - (-4)) + (3 - (-9)) + (4 - (-1)) + (1 - (-3))$
$= 4 + 13 + 12 + 5 + 4 = 38$。

在第二个测试用例中，受限于无法重建的道路限制，唯一的完美重建方案是“不重建任何道路”，因此最大美丽值为 $0$。

思路讲解

像这道题目，对于重建的这个约束太多。

Consider the case without any “accidents”, i.e., when there are no additional restrictions on the reconstructed streets.

我们可以先把所有对于重建边操作的限制，就是有一些边不能进行重建操作，给删除，我们会做了吗？（注意这里不能够把这个偶数条边的这个结果也给删了）

其实也没有那么简单，你首先要注意到，对于一维问题，成对的±，相当于一系列差分的和。那么，还需要特意去选吗？直接选全部为正的差分值不就好了？（连续选了两个或更多差分值，有重叠也没关系，可以使用我们下图的逆运算）

但是这个只能解决成对的 ± 问题呀，要是 ±+，以 + 结尾的不成对串如何解决呢？

来，我们仔细看看。只需要在末尾加一个 0，然后采用同样的贪心即可。

好，下面我们要正式解决这个问题了。

问题来到了 2D，我们发现有一个这个约束，就是，点的偶数边重建约束，这个还是有点烦的，怎么样去解决这个问题？

不难想到，如果一个点的边是否重建受到约束，我们能不能找到一个东西，其无论怎么样取，都符合约束呢？这样无论是贪心还是 dp，都会好解决的多。

Codeforces Round 1026 (Div. 2)-CF-1026-E. Melody

Codeforces Round 1081 (Div. 2)-CF-1081-E. Swap to Rearrange（按值进行图论建模）（欧拉回路）

通过这些题目，我们知道，如果说所有的点的度数都是偶数，组成的一定是一个欧拉回路（在无向联通图中）。

那么在这道题目中，题目所给我们的图，实际上是一个对偶图（就是边不相交的平面图，显然，网格图是对偶图），欧拉回路在对偶图中，实际上是一个割（这个是不难得出的，说白了，你在平面上一笔画出一条回路，当然能把平面划分为两部分，特别还要求你的这个路径是不会自相交的，因为所有边都互不相交）。注意，可以确定的是，这些欧拉回路

那既然是一个割，把一个面分割成了两部分，我们就想到了黑白染色。

这个时候求解为什么能想到小的单位面元？从更高的观点来看，其实这个是离散型二维格林公式。

格林公式与这道题目的关系

没问题。这就把格林公式的灵魂，在这道离散的网格题目中扒得干干净净。这才是这道题最深层的物理/数学本质。

一、 格林公式（Green’s Theorem）的核心灵魂是什么？

在高等数学里，格林公式极其优美，它建立了一个桥梁：

$$\oint_C (P dx + Q dy) = \iint_D \left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right) dx dy$$

别被公式吓到，它的灵魂用人话说就是：
“沿着一个闭合边界（外轮廓 $C$）转一圈的累积量，完全等于这个边界所包围的区域（内部面 $D$）里，每一个‘无穷小面元’的某种内在属性（旋度）的总和。”
为什么会这样？
因为如果你把区域 $D$ 切成无数个相邻的“小方格”，当你把所有小方格的“环量”加起来时，相邻方格的公共边界，一个是从左往右走，另一个是从右往左走，互相抵消了！ 最后没被抵消的，就只剩下最外面的那一圈大边界 $C$。

二、 题目中的“线积分”在哪？

题目定义的“美丽值”计算方式非常奇怪：
“在每一行 $i$ 中，选中的列 $c_1, c_2, c_3, c_4 \dots$ 交替加减：$+w_{i, c_1} - w_{i, c_2} + w_{i, c_3} \dots$”
我们用几何的眼光来看这个式子。
题目要求所有十字路口的联边数必须是偶数。在图论里，这意味着选出来的边，必定构成若干个闭合的环（多边形）。
假设我们选出了一个大矩形环（左边界在 $c_1$，右边界在 $c_2$，上边界在 $r_1$，下边界在 $r_2$）。
按照题目的计算规则：

• 对于位于 $c_1$ 的左垂直边，它排在第 1 个（奇数），前面是正号 $\rightarrow$ $+w$。
• 对于位于 $c_2$ 的右垂直边，它排在第 2 个（偶数），前面是负号 $\rightarrow$ $-w$。
• 同理，上方的水平边排第一 $\rightarrow$ $+v$。
• 下方的水平边排第二 $\rightarrow$ $-v$。
  发现了吗？
  这个交替加减的规则，本质上就是定义了一个有向的线积分规则：
  对于任何一个闭合形状，它的左边界贡献正，右边界贡献负，上边界贡献正，下边界贡献负。
  这就是格林公式等式左边的那个 $\oint_C (\dots)$！也就是“沿着外围边界的环量”！

---

三、 把格林公式用在离散网格上（微元化）

既然题目的美丽值求的是一个大环的“线积分（环量）”。
那么根据格林公式的思想，我们完全可以把这个大环，撕碎成无数个 $1 \times 1$ 的“无穷小面元（Basis / 小方块）”！
我们取网格中第 $i$ 行、第 $j$ 列的那个 $1 \times 1$ 的小方块。
如果我们把题目的线积分规则（左+，右-，上+，下-）强制套用到这个最微小的方块上，它就会产生一个属于它自己的“旋度”（也就是内在权值）：

$$Weight_{i,j} = \underbrace{w_{i,j}}{\text{左边界 (+) }} \quad \underbrace{- \quad w{i, j+1}}{\text{右边界 (-) }} \quad \underbrace{+ \quad v{i,j}}{\text{上边界 (+) }} \quad \underbrace{- \quad v{i+1,j}}_{\text{下边界 (-) }}$$

这就是那个 Basis 权值的确切由来！它就是离散版本的 $\left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right)$！

四、 完美闭环：局部加和 = 全局边界

现在，我们见证格林公式在离散网格上发威的瞬间。
如果我们选定了某几个连续的小方块（构成了一个区域 $D$）。
我们直接把这几个小方块的 $Weight$（旋度）全部加起来。
会发生什么？
比如方块 $(i,j)$ 和右边的方块 $(i, j+1)$ 被同时选中。

• $(i,j)$ 的旋度里有一项是 $- w_{i, j+1}$（它是右边界，取负）。
• $(i, j+1)$ 的旋度里有一项是 $+ w_{i, j+1}$（它是左边界，取正）。
  当这两个方块加在一起时，中间这条公共边 $w_{i, j+1}$ 直接抵消为 0！
  这在数学上绝对成立，没有任何例外：
  只要你把一堆小方块的权值加起来，它们内部所有共享的边必定全部互相抵消。最后加出来的总和，绝对等于这堆小方块构成的外轮廓边界，按照题目“左+右-上+下-”规则算出来的值！

$\iint_D (\text{小方块权值}) = \oint_{\partial D} (\text{题目要求的美丽值交替求和})$

结语

格林公式告诉我们：算复杂的边界太难了，算简单的内部面元再相加就容易了。
题目要求我们在无数种复杂的“偶数闭合边界”中找最大值，这极其困难，因为边界的形状千变万化，且互相牵制。
但格林公式赋予了我们降维打击的武器：
我们根本不去管什么边界和交替相加！我们直接算好每一个 $1 \times 1$ 小方块的固定内在权值（旋度），然后只要权值是正的，我就把它拿走（贪心选这个面元）。
你拿走的这堆正权值面元，它们的外边缘自然而然就生成了题目要求的最优闭合边界，且美丽值自动最大化！
这就是这道算法题背后最深沉、最优美的数学灵魂。

具体而言，如下图所示：

现在问题在于如何处理这个有些边不能进行重建操作？

那么上图已经讲的很清楚了，不能重建的边，就像是胶水，直接把这两块给粘起来，这条边就不会再操作了。唯一一个特殊点就是最边上的边就是和外部联通了，这里我们需要设置一个外部节点 out_node，把他和 out 连接在一起即可。

AC代码

AC
https://codeforces.com/contest/2205/submission/365321534

源代码

/**
 * Problem: F. Simons and Reconstructing His Roads
 * Contest: Codeforces Round 1083 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2205/problem/F
 * Created: 2026-03-03 15:33:08
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct X_Y {
    ll x,y;
    bool operator<(const X_Y &o) const {
        if (x!=o.x) {
            return x<o.x;
        }
        return y<o.y;
    }
    bool operator==(const X_Y &o) const {
        return o.x==x && o.y==y;
    };
};
void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<ll>> w_i(N+2,vector<ll>(M+2));
    for (int i=1;i<=N-1;++i) {
        for (int j=1;j<=M;++j) {
            cin>>w_i[i][j];
        }
    }
    vector<vector<ll>> w_j(N+2,vector<ll>(M+2));
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=M-1;++j) {
            cin>>w_j[i][j];
        }
    }
    vector<vector<char>> valid_i(N+2,vector<char>(M+2));
    for (int i=1;i<=N-1;++i) {
        for (int j=1;j<=M;++j) {
            cin>>valid_i[i][j];
            valid_i[i][j]-='0';
        }
    }
    vector<vector<char>> valid_j(N+2,vector<char>(M+2));
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=M-1;++j) {
            cin>>valid_j[i][j];
            valid_j[i][j]-='0';
        }
    }
    map<X_Y,X_Y> fa;
    map<X_Y,ll> node_val;
    // 我们采用左上角标号来指定小方块
    for (int i=1;i<=N-1;++i) {
        for (int j=1;j<=M-1;++j) {
            node_val[{i,j}]=w_i[i][j]+w_j[i][j]-w_i[i][j+1]-w_j[i+1][j];
        }
    }
    auto find=[&](auto && self,X_Y x) -> X_Y {
        auto it=fa.find(x);
        if (it==fa.end()) {
            return x;
        }
        // if (it->second==x) {
        //     return x;
        // }
        return fa[x]=self(self,fa[x]);
    };
    auto merge=[&](X_Y u,X_Y v) -> void {
        auto fau=find(find,u),fav=find(find,v);
        if (fau==fav) {
            return;
        }
        fa[fau]=fav;
        node_val[fav]+=node_val[fau];
    };
    X_Y out_node={N+2,M+2};
    node_val[out_node]=-INF;
    // 我们采用左上角标号来指定小方块
    for (int i=1;i<=N-1;++i) {
        for (int j=1;j<=M;++j) {
            // cin>>valid_i[i][j];
            // valid_i[i][j]-='0';
            // （i，j） （i+1，j）
            if (!valid_i[i][j]) {
                if (j==1) {
                    // node_val[{i,j}]=-INF;
                    merge({i,j},out_node);
                    continue;
                }
                if (j==M) {
                    // node_val[{i,j-1}]=-INF;
                    merge({i,j-1},out_node);
                    continue;
                }
                merge({i,j-1},{i,j});
            }
        }
    }
    for (int i=1;i<=N;++i) {
        for (int j=1;j<=M-1;++j) {
            // cin>>valid_i[i][j];
            // valid_i[i][j]-='0';
            // （i，j） （i+1，j）
            if (!valid_j[i][j]) {
                if (i==1) {
                    // node_val[{i,j}]=-INF;
                    merge({i,j},out_node);
                    continue;
                }
                if (i==N) {
                    // node_val[{i-1,j}]=-INF;
                    merge({i-1,j},out_node);
                    continue;
                }
                merge({i-1,j},{i,j});
            }
        }
    }
    ll ans=0;
    for (auto [node,v]:node_val) {
        if (node!=find(find,node)) {
            continue;
        }
        // 必须要是根，才能继续操作
        if (v>0) {
            ans+=v;
        }
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2205/submission/365321534

1
2 4
4 23 1 35
6 12 -17
-14 1 -40
0100
000
101




*/

心路历程（WA，TLE，MLE……）

在并查集中，直接改动节点的值是非常幼稚的，因为你不知道他是不是根节点，当然你可以 find 后改根节点。

AC

https://codeforces.com/contest/2205/submission/365204709

AI 代码确实是没什么问题。