题解：AT_abc461_g [ABC461G] Graph Problem 2026

· · 题解

[ABC461G] Graph Problem 2026 Solution

Part 0th. 简化题意

瞪眼法可以发现无论什么情况下最劣情况的答案都是 N \times 1013。

观察样例，感觉最优的情况下 W_i 的值只能取 0,1013,2026。例如在如下的情况，取 0,2026 一定比取 1,2025 优秀。

通过线性规划边界分析可以证明：存在一个最优解，每个点的权值只可能是 W_i \in {0,1013,2026}。

不知道什么是线性规划边界分析的点这里。 <- Click

:::info[Deepseek 的严谨证明] 记 C = 2026，a = C/2 = 1013。原始问题为线性规划：

\begin{aligned} \text{maximize} \quad & \sum_{i=1}^n W_i \\ \text{subject to} \quad & 0 \le W_i \le C, \quad \forall i,\\ & W_u + W_v \le C, \quad \forall (u,v)\in E. \end{aligned}

1. 对偶问题与互补松弛

引入对偶变量：

对偶规划为：

\begin{aligned} \text{minimize} \quad & \sum_{i=1}^n C\beta_i + \sum_{e\in E} C\gamma_e \\ \text{subject to} \quad & \alpha_i - \beta_i + \sum_{e\ni i} \gamma_e = 1, \quad \forall i,\\ & \alpha_i,\beta_i,\gamma_e \ge 0. \end{aligned}

由线性规划的强对偶定理，存在最优原始解 \{W_i\} 和对偶解 \{\alpha_i,\beta_i,\gamma_e\} 满足互补松弛条件：

2. 分析内部点

取一个最优解 \{W_i\}（可假定是极值点，但互补松弛条件对任何最优解均成立）。考虑某个顶点 i 满足 0 < W_i < C。由互补松弛，\alpha_i = 0 且 \beta_i = 0，代入对偶约束得：

\sum_{e\ni i} \gamma_e = 1. \tag{1}

左边是非负项之和为 1，故至少存在一个邻边 e=(i,j) 使得 \gamma_e > 0。再由互补松弛，\gamma_e > 0 意味着该边约束紧，即

W_i + W_j = C. \tag{2}

从而 W_j = C - W_i。注意 W_j 同样满足 0<W_j<C（因为 0<W_i<C，且若 W_i \neq a 则 W_j\neq a；若 W_i = a 则 W_j = a，仍属于内部）。因此，每个与 i 相邻且 \gamma_e>0 的顶点 j 也处于内部，并且 W_j 由 W_i 唯一确定。进一步，对 W_j 应用相同推理：它的所有紧边邻居也由它决定，以此类推。

3. 连通分量结构

考虑所有内部点（即 0<W<C）以及它们之间满足 \gamma_e>0 的边构成的子图 H。由 (2) 可知，在 H 中每条边 (u,v) 满足 W_u+W_v=C，且顶点值在 C-W_u 之间交替。这表明 H 是二分图：将顶点按与某个固定点的距离（沿边）的奇偶性分为两部，一部值为 t，另一部值为 C-t，其中 t 是该连通分量中某个顶点的值。若 H 包含奇环，则沿着奇环走一圈会得到 t = C-t，即 t = C/2 = a，此时所有顶点值为 a，且奇环不导致矛盾（所有顶点相等时边约束紧且合法）。因此，H 的每个连通分量要么是偶图（可二染色），要么所有顶点值相等且为 a。

4. 最大化总和的调整

考虑 H 的一个连通分量，设其顶点集为 S，边集为 E_S，且对每条边有 W_u+W_v=C。设分量中一部顶点数为 A，另一部为 B，对应值分别为 t 和 C-t（若分量全为 a，则视为 A=B 且 t=a 的特殊情况）。该分量的总和为

\sum_{i\in S} W_i = A t + B(C-t) = B C + (A-B)t.

在保持其他分量不变的前提下，我们可以调整 t 的值（前提是调整后仍满足与分量外顶点的边约束，但那些边要么非紧，要么也可调整）。为达到全局最优，我们可以在可行范围内选择 t 最大化该分量的贡献。由于表达式关于 t 是线性的，斜率 A-B 为常数，最大值在端点 t=0 或 t=C 处取得，除非 A=B。若 A=B，则总和 = BC 与 t 无关，此时我们可以任意选取 t，例如取 t=0（从而该分量所有点变为 0 或 C）或取 t=a（全为 a），总和不改变。

因此，总存在一个最优解，使得每个连通分量要么取极值 0 或 C（即顶点值 \in \{0,C\}），要么全取 a。特别地，每个顶点的值属于 \{0, a, C\}。

5. 回到原题

由于 C = 2026，a = 1013，我们证明了存在最优解满足

W_i \in \{0,\;1013,\;2026\}, \quad \forall i.

证毕。 :::

然后我们就可以把这一题压缩一下，变成给一个 N 个点 M 条边的图每个点赋值为 W_i \in [0,2] 使得任意一个 W_u = 2 的所有相邻节点 W_v = 0。

Part 2nd. 问题转化

这不就是一个裸的二分图吗？

这种问题就可以直接用二分图解决了。

我们将 N 个节点 [0,N-1] 作为二分图的子集 X，将 [N,2 \times N - 1] 作为二分图的子集 Y，那么就可以在上面跑匈牙利算法了。

注意，二分图问题中你只需要从 X 子集中的点连到 Y 子集中的点。

当然，匈牙利 \mathcal{O}(nE) 的复杂度显然是过不了这一题的，骗你的其实匈牙利跑的飞快的根本卡不掉所以要使用 Hopcroft-Karp 算法。

最后我们设最大匹配答案为 K，那么最后的答案是 (2 \times N - K) \times 1013。

Part 3rd. 最终代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = (5e4 + 10) * 2;
const int INF = 1e9 + 91;
int n, m, pairU[MAXN], pairV[MAXN];
int dis[MAXN];
vector<int>G[MAXN];
bool bfs() {
    queue<int>q;
    for (int i = 0; i < n; i++) {
        if (pairU[i] == -1) {
            dis[i] = 0;
            q.push(i);
        } else {
            dis[i] = INF;
        }
    }
    bool flag = false;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto v : G[u]) {
            if (pairV[v] != -1 and dis[pairV[v]] == INF) {
                dis[pairV[v]] = dis[u] + 1;
                q.push(pairV[v]);
            } else if (pairV[v] == -1) {
                flag = true;
            }
        }
    }
    return flag;
}
bool dfs(int s) {
    for (int v : G[s]) {
        if (pairV[v] == -1 || (dis[pairV[v]] == dis[s] + 1 && dfs(pairV[v]))) {
            pairU[s] = v;
            pairV[v] = s;
            return true;
        }
    }
    dis[s] = INF;
    return false;
}
int HK() {
    fill(pairU, pairU + 2 * n, -1);
    fill(pairV, pairV + 2 * n, -1);
    int ans = 0;
    while (bfs()) {
        for (int u = 0; u < n; u++) {
            if (pairU[u] == -1 && dfs(u)) {
                ans++;
            }
        }
    }
    return ans;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G[u - 1].emplace_back(v + n - 1);
        G[v - 1].emplace_back(u + n - 1);
    }
    cout << (2 * n - HK()) * 1ll * 1013ll ;
    return 0;
}