Codeforces Round 1083 (Div. 2)——CF-2205-F. Simons and Reconstructing His Roads（遇到一道题目没有思路，可以先降低约束试一试）（+-+-，需要想到差分）（对割的理解以及使用）（格林公式的应用） · znzryb
## 题目大意
**题目大意**
给定一个 $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$。
1. 对于每一行 $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$ 累加到美丽值中。
1. 对于每一列 $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](/2026/02/23/20260223-e1ba2987)
[Codeforces Round 1081 (Div. 2)-CF-1081-E. Swap to Rearrange（按值进行图论建模）（欧拉回路）](/2026/02/22/20260222-b6e20294)
通过这些题目，我们知道，如果说**所有的点的度数都是偶数，组成的一定是一个欧拉回路**（在无向联通图中）。
那么在这道题目中，题目所给我们的图，实际上是一个**对偶图**（就是边不相交的平面图，显然，网格图是对偶图），欧拉回路在对偶图中，**实际上是一个割**（这个是不难得出的，说白了，你在平面上一笔画出一条回路，当然**能把平面划分为两部分**，特别还要求你的这个路径是不会自相交的，因为所有边都互不相交）。注意，可以确定的是，这些欧拉回路
那既然是一个割，把**一个面分割成了两部分**，我们就想到了**黑白染色**。
这个时候求解为什么能想到小的单位面元？从更高的观点来看，其实这个是**离散型二维格林公式**。
::: 格林公式与这道题目的关系
没问题。这就把格林公式的灵魂，在这道离散的网格题目中扒得干干净净。这才是这道题最深层的物理/数学本质。
---
### 一、 格林公式（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](https://codeforces.com/contest/2205/submission/365321534)
::: 源代码
```cpp
/**
* 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](https://codeforces.com/contest/2205/submission/365204709)
AI 代码确实是没什么问题。