AtCoder Beginner Contest 461 题解

项目	内容
比赛时间	2026-06-06
比赛链接	https://atcoder.jp/contests/abc461
题目数量	A–G 共 7 题

比赛概览

本场整体难度由浅入深：A、B 为签到题（简单比较、排列求逆）；C 是"颜色代表元 + 贪心"；D 是经典的"枚举上下边界 + 前缀和 + 双指针"计数；E 考验增量维护黑格数与用树状数组去重的能力；F 的关键在于"约数个数最多 2304 个、集合大小最多 14"的观察，配合计数 DP；G 需要把图论问题转化为二分图最大匹配，并用 König 定理给出优雅证明。其中 D、E、F、G 值得重点掌握。

---

A - Armor

题目链接：https://atcoder.jp/contests/abc461/tasks/abc461_a

题目大意

给定两个整数 $A, D$（$1 \le A, D \le 100$）。铠甲能抵挡所有力量不超过 $D$ 的攻击。问力量为 $A$ 的攻击能否被挡下，能则输出 Yes，否则输出 No。

思路

直接按题意比较即可：若 $A \le D$，铠甲能挡下，输出 Yes；否则输出 No。

唯一需要注意的易错点是边界：当 $A = D$ 时攻击力量恰好等于防御上限，依然能被挡下（见样例 2），因此比较要用 $\le$ 而不是 $<$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int A, D;
    cin >> A >> D;
    cout << (A <= D ? "Yes" : "No") << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

---

B - The Honest Woodcutters

题目链接：https://atcoder.jp/contests/abc461/tasks/abc461_b

题目大意

$N$ 个樵夫各有 $1$ 把斧子，全部掉进池塘后捞出了 $N$ 把斧子。樵夫 $i$ 声称"斧子 $A_i$ 是我的"；而女神知道斧子 $i$ 真正的主人是樵夫 $B_i$。问是否所有樵夫都在说真话。输入保证 $A_1,\dots,A_N$ 与 $B_1,\dots,B_N$ 都各是 $1\sim N$ 的一个排列。

思路

关键观察：斧子 $i$ 的主人是樵夫 $B_i$，而樵夫 $B_i$ 声称自己拥有斧子 $A_{B_i}$。因此樵夫 $B_i$ 说真话当且仅当"斧子 $A_{B_i}$ 的主人确实是 $B_i$"，即

$$B_{A_{B_i}} = B_i .$$

由于 $B$ 是排列（一一对应），上式等价于

$$A_{B_i} = i \qquad (i = 1, 2, \dots, N).$$

所以只需逐一检查 $i=1,\dots,N$ 是否都有 $A_{B_i} = i$，一旦发现不满足即可判定为 No。

换个角度看，这等价于验证 $A$ 与 $B$ 互为逆排列（$A \circ B = \mathrm{id}$）。由于排列的逆是唯一的，且"$A$ 是 $B$ 的逆"与"$B$ 是 $A$ 的逆"互为充要条件，因此也可以等价地检查 $B_{A_i} = i$ 是否对所有 $i$ 成立。注意 $A$ 和 $B$ 都是排列，这一性质在证明中起到关键作用（没有它，仅检查其中一部分 $i$ 是不够的）。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) cin >> B[i];

    for (int i = 1; i <= N; i++) {
        if (A[B[i]] != i) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

---

C - Variety

题目链接：https://atcoder.jp/contests/abc461/tasks/abc461_c

题目大意

$N$ 颗宝石，第 $i$ 颗颜色为 $C_i$、价值为 $V_i$。从中选择恰好 $K$ 颗，要求选出的宝石中至少包含 $M$ 种不同颜色，求所选宝石总价值的最大值。$1 \le M \le K \le N \le 2\times 10^5$，$1 \le V_i \le 10^9$，输入保证至少存在 $M$ 种颜色的宝石。

思路

本题的核心是下面这个关键引理：

（★）存在一组最优解，它包含每种颜色中价值最高的那颗宝石（若并列任取其一），并且包含全部 $M$ 颗"被标记"的颜色代表。

构造如下：按颜色分组，对每种颜色取价值最高的宝石作为该颜色的"代表"；把所有代表按价值从大到小排序，取前 $M$ 颗标记出来（称为"标记宝石"）。

引理（★）的证明。 任取一组满足条件的最优选法（$K$ 颗、颜色种数 $\ge M$）。对选法中出现的每种颜色：若该颜色的代表未被选中，就取该颜色中任一颗已选宝石，把它替换成代表——由于代表是该颜色中价值最高的，总价值不下降，而颜色种数不变。反复操作后，选法中的每种颜色都以代表身份入选，因此至少选入了 $M$ 颗代表。此时若仍有标记宝石未被选中，说明当前至少选了一颗"未标记的代表"；又因为标记宝石的价值不小于任何未标记的代表，用标记宝石逐颗替换未标记代表，总价值单调不减，最终得到一组包含全部 $M$ 颗标记宝石的最优解，且始终满足约束。证毕。

由（★），算法如下：

1. 取出 $M$ 颗标记宝石。它们来自 $M$ 种不同颜色，已满足"至少 $M$ 种颜色"的约束。
2. 对剩余的所有宝石（包括各颜色中除代表外的宝石，以及排名在第 $M$ 名之后的那些代表）按价值从大到小排序，再取前 $K-M$ 颗。

答案即为两部分之和。由于约束已被标记宝石满足，其余宝石可以放心地只挑价值最大的 $K-M$ 颗。

一个小易错点：价值之和可能达到 $K \times 10^9 \approx 2\times 10^{14}$，必须用 64 位整数（见样例 3）。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, M;
    cin >> N >> K >> M;
    vector<vector<ll>> group(N + 1);
    for (int i = 0; i < N; i++) {
        int C;
        ll V;
        cin >> C >> V;
        group[C].push_back(V);
    }

    vector<ll> top, tail;
    for (int c = 1; c <= N; c++) {
        if (group[c].empty()) continue;
        sort(group[c].begin(), group[c].end(), greater<ll>());
        top.push_back(group[c][0]);          // 该颜色的代表
        for (int i = 1; i < (int)group[c].size(); i++)
            tail.push_back(group[c][i]);     // 该颜色的其余宝石
    }

    sort(top.begin(), top.end(), greater<ll>());
    for (int i = M; i < (int)top.size(); i++) tail.push_back(top[i]);
    sort(tail.begin(), tail.end(), greater<ll>());

    ll ans = 0;
    for (int i = 0; i < M; i++) ans += top[i];
    for (int i = 0; i < K - M; i++) ans += tail[i];
    cout << ans << '\n';
    return 0;
}

官方题解给出的 Python 实现（思路与上述一致）：

N, K, M = map(int, input().split())
t = [[] for _ in range(N + 1)]
for i in range(N):
    C, V = map(int, input().split())
    t[C].append(V)

top = []
tail = []
for r in t:
    if len(r) > 0:
        r.sort(reverse=True)
        top.append(r[0])
        tail += r[1:]

top.sort(reverse=True)
tail += top[M:]
tail.sort(reverse=True)
print(sum(top[:M]) + sum(tail[:K - M]))

复杂度分析

• 时间复杂度：$O(N \log N)$（瓶颈在各次排序）
• 空间复杂度：$O(N)$

---

D - Count Subgrid Sum = K

题目链接：https://atcoder.jp/contests/abc461/tasks/abc461_d

题目大意

给定一个 $H\times W$ 的 01 网格，求所有"元素和为 $K$"的矩形子区域个数。即求满足 $1\le r_1\le r_2\le H$、$1\le c_1\le c_2\le W$ 且对应子矩形内数字之和恰好为 $K$ 的四元组 $(r_1,c_1,r_2,c_2)$ 的数量。$1 \le H, W \le 500$，$0 \le K \le HW$。

思路

直接枚举四个边界并对子矩形求和是 $O(H^2W^2)$，不可行。标准技巧是固定上下两行、对列做压缩：

固定矩形的上边 $u$ 与下边 $d$，令

$$A_j = \sum_{i=u}^{d} [S[i][j] = 1]$$

表示第 $j$ 列在 $u\sim d$ 行内的 1 的个数，并取前缀和

$$B_j = A_1 + A_2 + \cdots + A_j \qquad (B_0 = 0).$$

则 $B_r - B_l$ 恰好等于"行 $u\sim d$、列 $l+1\sim r$"这个子矩形的和。于是问题转化为：对每一组 $(u,d)$，统计满足

$$B_r - B_l = K, \qquad 0 \le l < r \le W$$

的无序对 $(l,r)$ 的个数。

因为 $A_j \ge 0$，前缀和 $B$ 是非递减的，这让我们可以用**双指针（滑动窗口）**快速计数。对固定的 $l$，定义

• $r_1(l)$ = 最小的 $r$ 使得 $B_r - B_l \ge K$；
• $r_2(l)$ = 最小的 $r$ 使得 $B_r - B_l > K$。

则满足 $B_r - B_l = K$ 的 $r$ 恰好落在区间 $[r_1(l), r_2(l))$ 内，个数为 $r_2(l) - r_1(l)$。当 $l$ 增大时，$B_l$ 不降，因此 $r_1, r_2$ 也单调不降，两个指针各自全程最多移动 $O(W)$ 次，每个 $l$ 摊还 $O(1)$。

于是总复杂度 $O(H^2 W)$：先 $O(HW)$ 预处理每一列的纵向前缀和（$O(1)$ 得到 $A_j$），再对 $O(H^2)$ 组 $(u,d)$ 各做一次 $O(W)$ 的双指针扫描。

几个注意点：

• 当 $H > W$ 时可以把网格转置，让 $H$ 成为较小的维度，复杂度变为 $O(\min(H,W)^2\max(H,W))$，最坏情况（$H=W=500$）不变，但能显著改善"长条"网格。
• $K = 0$ 时数的是满足 $B_r = B_l$ 的区间，上述双指针逻辑仍然正确（此时 $r_1$ 恒等于 $l+1$）。
• 子矩形总数约为 $\binom{H+1}{2}\binom{W+1}{2} \approx 1.56\times 10^{10}$，答案必须用 64 位整数。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 统计 0 <= l < r <= n-1 且 b[r] - b[l] == k 的对数（b 非递减）
ll countPairs(const vector<ll>& b, ll k) {
    int n = (int)b.size();
    ll res = 0;
    int r1 = 1, r2 = 1;
    for (int l = 0; l + 1 < n; l++) {
        r1 = max(r1, l + 1);
        r2 = max(r2, l + 1);
        while (r1 < n && b[r1] - b[l] < k) r1++;
        while (r2 < n && b[r2] - b[l] <= k) r2++;
        res += r2 - r1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    ll K;
    cin >> H >> W >> K;
    vector<string> S(H);
    for (int i = 0; i < H; i++) cin >> S[i];

    // colSum[i][j] = 前 i 行中第 j 列含有的 1 的个数
    vector<vector<int>> colSum(H + 1, vector<int>(W + 1, 0));
    for (int j = 1; j <= W; j++) {
        for (int i = 1; i <= H; i++) {
            colSum[i][j] = colSum[i - 1][j] + (S[i - 1][j - 1] == '1');
        }
    }

    ll ans = 0;
    for (int u = 1; u <= H; u++) {
        for (int d = u; d <= H; d++) {
            vector<ll> b(W + 1, 0);
            for (int j = 1; j <= W; j++) {
                b[j] = b[j - 1] + (colSum[d][j] - colSum[u - 1][j]);
            }
            ans += countPairs(b, K);
        }
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(H^2 W)$；若先转置使 $H \le W$，则为 $O(\min(H,W)^2\max(H,W))$
• 空间复杂度：$O(HW)$（纵向前缀和）

---

E - E-liter

题目链接：https://atcoder.jp/contests/abc461/tasks/abc461_e

题目大意

有一个 $N\times N$ 的网格，初始全为白色。按顺序处理 $Q$ 个操作，操作有两种：类型 1 将第 $R$ 行整行涂黑；类型 2 将第 $C$ 列整列涂白。每个操作执行完后输出当前黑格数量。$N, Q \le 3\times 10^5$。

思路

每次操作后都重新扫描整个网格显然不行（$O(N^2Q)$）。正确思路是增量维护黑格数量的变化：每次操作只需回答"这次操作让黑格数增加/减少了多少"，而回答该问题只需知道此前某些行/列被操作过的情况。

先看类型 1（把第 $R$ 行涂黑）增加的黑格数：

• 若第 $R$ 行从未被涂黑过：黑格只会由"整行涂黑"产生，而第 $R$ 行从未被涂黑，故该行此刻全白，涂黑后增加 $N$ 个黑格。
• 否则，设上一次涂黑第 $R$ 行发生在第 $\mathrm{last}$ 次操作。那次操作之后第 $R$ 行整行是黑的；此后凡是"被类型 2 涂白过"的列，其第 $R$ 行的格子又重新变白。因此本次增加的黑格数 = 自第 $\mathrm{last}$ 次操作以来被类型 2 操作过的不同列数。

类型 2（把第 $C$ 列涂白）减少的黑格数与之对称：

• 若第 $C$ 列从未被涂白过：第 $C$ 列中，凡所在行被涂黑过的格子此刻都是黑的，故减少量 = 到目前为止被类型 1 操作过的不同行数。
• 否则，设上一次涂白第 $C$ 列发生在第 $\mathrm{last}$ 次操作。此后被涂黑过的行会让第 $C$ 列对应格子变黑，故减少量 = 自第 $\mathrm{last}$ 次以来被类型 1 操作过的不同行数。

剩下的问题是如何快速求"某个下标区间内被操作过的不同行/列数"。由于一行（列）可能被操作多次，但我们只关心其最后一次操作的位置，因此可以用两棵长度为 $Q$ 的树状数组维护：

• $f_0[i] = 1$ 表示第 $i$ 次操作是目前"最后一次涂黑其所在行"的类型 1 操作；
• $f_1[i] = 1$ 表示第 $i$ 次操作是目前"最后一次涂白其所在列"的类型 2 操作。

这样区间 $[l, r)$ 内 $f$ 的和，恰等于该时间区间内被操作过的不同行（列）数。处理每条操作时，先按上面的公式用区间和更新黑格数，再把自己在该行/列上的旧标记删除、在当前时刻插入新标记（同时维护 last[t][x] 数组记录该行/列上次被操作的时刻）。

（补充说明：官方题解给出的 Python 示例代码在"某列首次被涂白"的分支中写成了 black += N，这与正确逻辑相悖，直接用其跑样例会得到错误结果；本文按正确的逻辑给出 C++ 实现。）

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BIT {
    int n;
    vector<int> bit;
    BIT(int n) : n(n), bit(n + 1, 0) {}
    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }
    int sum(int idx) {               // 前缀和 [1, idx]
        int s = 0;
        for (; idx > 0; idx -= idx & -idx) s += bit[idx];
        return s;
    }
    int sum(int l, int r) {          // 区间和 [l, r)
        return sum(r - 1) - sum(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    BIT bit[2] = {BIT(Q + 1), BIT(Q + 1)};
    vector<int> last[2];
    last[0].assign(N + 1, -1);   // 每行上一次被涂黑的时刻
    last[1].assign(N + 1, -1);   // 每列上一次被涂白的时刻

    ll black = 0;
    for (int i = 1; i <= Q; i++) {
        int t, x;
        cin >> t >> x;            // t=1: 涂黑第 x 行；t=2: 涂白第 x 列
        t--;
        if (last[t][x] == -1) {
            if (t == 0) {
                black += N;                   // 首次涂黑该行：整行由白变黑
            } else {
                black -= bit[0].sum(1, i);    // 首次涂白该列：减去已被涂黑的不同行数
            }
        } else {
            int kind = bit[1 - t].sum(last[t][x], i);   // 自上次操作以来新增的不同行/列数
            black += (t == 0 ? kind : -kind);
            bit[t].add(last[t][x], -1);       // 移除旧标记
        }
        bit[t].add(i, 1);                     // 插入新标记
        last[t][x] = i;
        cout << black << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O((N + Q)\log Q)$（每条操作常数次 $O(\log Q)$ 的树状数组操作）
• 空间复杂度：$O(N + Q)$

---

F - Total Product is N

题目链接：https://atcoder.jp/contests/abc461/tasks/abc461_f

题目大意

给定正整数 $N \le 10^{10}$。称非空正整数序列 $A$ 为"好序列"，若其所有元素互不相同且乘积等于 $N$。一个序列的得分是各元素之和。求所有好序列的得分之和，对 $998244353$ 取模。

思路

本题的两个关键转化：

转化 1：元素必为 $N$ 的约数，且约数个数很少。 好序列中每个元素都整除 $N$。对 $N \le 10^{10}$，约数个数最多只有 $2304$ 个，因此可以枚举全部约数 $d_1,\dots,d_K$（$K \le 2304$）。

转化 2：得分与顺序无关，无序集合 + 阶乘。 同一组元素 $S$ 的任意排列得分相同（都等于 $\sum_{x\in S}x$）。因此全部好序列得分之和等于

$$\sum_{b=1}^{\infty} b! \times \left(\sum_{\substack{S\subseteq\{d_i\},\ |S|=b,\ \prod S=N}} \sum_{x\in S} x\right).$$

于是只需对"无序集合"做 DP。设 $dp0[b][c]$ 为用 $b$ 个不同约数、乘积为 $c$ 的选法数，$dp1[b][c]$ 为这些选法对应"元素和"的总和。按约数从小到大逐个处理，每个约数 $d$ 要么不选、要么选入（0/1 背包）。若当前乘积为 $c$、选入 $d$ 后乘积为 $cd$（要求 $cd$ 是 $N$ 的约数）：

$$dp0[b][cd] \mathrel{+}= dp0[b-1][c],$$

$$dp1[b][cd] \mathrel{+}= dp1[b-1][c] + dp0[b-1][c]\cdot d .$$

第二式成立是因为：新集合的元素和 = 旧集合元素和 $+ d$，对所有 $dp0[b-1][c]$ 个选法求和即得。

$b$ 的上界为什么只有 14？ 一组互不相同的正整数，若不含 1，乘积至少是 $2\cdot 3\cdots(b+1) = (b+1)!$；由于 $13! \approx 6.2\times 10^9 < 10^{10} < 14!$，不含 1 时最多 13 个元素，加上 1 最多 14 个。因此 $b \le 14$，这一维极小。

实现要点：用"约数值 → 排名"的哈希表把乘积 $cd$ 映射回下标；对 $b$ 从大到小更新，保证每个约数最多被选一次。初始 $dp0[0][1] = 1$。最终答案

$$\mathrm{Ans} = \sum_{b=1}^{14} dp1[b][N]\cdot b! \pmod{998244353}.$$

复杂度 $O(K^2 \cdot 14)$，其中 $K \le 2304$，约 $7.4\times 10^7$ 量级，足够快；由于循环中带"$cd \le N$ 且 $cd \mid N$"的剪枝，实际运算量远小于该上界。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;

    vector<ll> divs;
    for (ll x = 1; x * x <= N; x++) {
        if (N % x == 0) {
            divs.push_back(x);
            if (x * x != N) divs.push_back(N / x);
        }
    }
    sort(divs.begin(), divs.end());
    int K = (int)divs.size();

    unordered_map<ll, int> id;
    for (int i = 0; i < K; i++) id[divs[i]] = i;

    const int MAXB = 14;                 // b 的最大取值
    vector<vector<ll>> dp0(MAXB + 1, vector<ll>(K, 0));
    vector<vector<ll>> dp1(MAXB + 1, vector<ll>(K, 0));
    dp0[0][id[1]] = 1;

    for (ll d : divs) {
        for (int b = MAXB; b >= 1; b--) {          // 从大到小：每个约数最多用一次
            for (int ci = 0; ci < K; ci++) {
                ll c = divs[ci];
                if (c > N / d) break;              // 此后 c*d > N
                ll nd = c * d;
                if (N % nd != 0) continue;         // 乘积必须是 N 的约数
                int ni = id[nd];
                dp0[b][ni] = (dp0[b][ni] + dp0[b - 1][ci]) % MOD;
                dp1[b][ni] = (dp1[b][ni] + dp1[b - 1][ci]
                              + dp0[b - 1][ci] * (d % MOD)) % MOD;
            }
        }
    }

    vector<ll> fact(MAXB + 1, 1);
    for (int i = 1; i <= MAXB; i++) fact[i] = fact[i - 1] * i % MOD;

    ll ans = 0;
    for (int b = 1; b <= MAXB; b++) {
        ans = (ans + dp1[b][id[N]] * fact[b]) % MOD;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(K^2 \cdot B)$，其中 $K \le 2304$ 为 $N$ 的约数个数、$B = 14$ 为元素个数上界（含剪枝后实际远小于此）
• 空间复杂度：$O(K \cdot B)$

---

G - Graph Problem 2026

题目链接：https://atcoder.jp/contests/abc461/tasks/abc461_g

题目大意

$N$ 个顶点、$M$ 条边的简单无向图。给每个顶点 $j$ 赋非负整数权值 $0 \le W_j \le 2026$，要求对每条边 $(u,v)$ 满足 $W_u + W_v \le 2026$。求 $\sum_{j=1}^{N} W_j$ 的最大值。$N, M \le 5\times 10^4$。

思路

第一步：构造二分图，把原问题与最大独立集联系起来。

建立 $2N$ 个新顶点 $A_1,\dots,A_N$ 和 $B_1,\dots,B_N$。对原图的每条边 $(u,v)$，在新图中连边 $A_u - B_v$ 与 $A_v - B_u$。设新图的最大独立集大小为 $\mathrm{MIS}$，则原问题的答案恰为 $1013 \times \mathrm{MIS}$。

先证下界（构造可行解）。记 $f(x)=1$ 当且仅当 $x \in \mathrm{MIS}$，令

$$W_i = 1013 \times \big(f(A_i) + f(B_i)\big).$$

由于 $\mathrm{MIS}$ 是独立集，$A_u$ 与 $B_v$ 不能同时属于 $\mathrm{MIS}$，所以 $f(A_u)+f(B_v)\le 1$；同理 $f(A_v)+f(B_u)\le 1$。于是对每条原边 $(u,v)$，

$$W_u + W_v = 1013\big(f(A_u)+f(B_v) + f(A_v)+f(B_u)\big) \le 2026,$$

即这组权值合法，其总和为 $1013 \times \mathrm{MIS}$。故最大值 $\ge 1013\cdot\mathrm{MIS}$。

再证上界。任取一组合法权值 $W$。设新图去掉孤立点后的最小边覆盖为 $\mathrm{MEC}$，孤立点（对应原图中的孤立顶点，每个贡献 $A_i, B_i$ 两个新点）个数为 $K$。对二分图有恒等式

$$|\mathrm{MIS}| = |\mathrm{MEC}| + K.$$

（理由：无孤立点二分图中，最大匹配 $+$ 最小边覆盖 $=$ 顶点数；König 定理给出最大匹配 $=$ 最小点覆盖；最大独立集 $=$ 顶点数 $-$ 最小点覆盖。）

每个原顶点 $i$ 对应 $A_i, B_i$ 两个"权位"。边覆盖中每条边覆盖两个新顶点，非孤立新顶点都被覆盖到，因此

$$2\sum_{i=1}^{N}W_i \le \sum_{(u,v)\in \mathrm{MEC}}(W_u + W_v) + \sum_{k=1}^{K} W_{P_k},$$

其中 $P_1,\dots,P_K$ 为孤立新顶点。每条边覆盖边都来自原图的一条边，故 $W_u+W_v \le 2026$；每个孤立顶点权值 $\le 2026$。于是

$$2\sum_{i=1}^{N}W_i \le 2026\,|\mathrm{MEC}| + 2026\,K = 2026\,|\mathrm{MIS}|,$$

即 $\sum_i W_i \le 1013\,|\mathrm{MIS}|$。综上，最大值恰好等于 $1013 \times \mathrm{MIS}$。

（另一种思路是线性规划松弛下的半整性：可证明存在最优解使所有权值都落在 $\{0, 1013, 2026\}$ 中，随后同样化为二分图上的匹配/最小割问题，与本结论殊途同归。实现时采用上述更直接的构造。）

第二步：计算最大独立集。

新图是二分图（左部 $A$、右部 $B$）。由 König 定理，

$$\mathrm{MIS} = 2N - (\text{新图最大匹配}).$$

用 Hopcroft–Karp 算法求最大匹配，复杂度 $O(M\sqrt{N})$，足以通过 $N, M \le 5\times 10^4$。

验证样例 1：$N=3$，边 $(1,2),(2,3)$。新图最大匹配为 2（例如 $A_1\!-\!B_2,\ A_2\!-\!B_1$），答案为 $1013\times(6-2)=4052$，与样例一致。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct HopcroftKarp {
    int n, m;                        // 左部 n 个点、右部 m 个点
    vector<vector<int>> adj;         // adj[u] = 与左部 u 相邻的右部顶点
    vector<int> matchL, matchR, dist;

    HopcroftKarp(int n, int m) : n(n), m(m), adj(n) {}

    bool bfs() {
        queue<int> q;
        for (int u = 0; u < n; u++) {
            if (matchL[u] == -1) { dist[u] = 0; q.push(u); }
            else dist[u] = -1;
        }
        bool reachable = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                int w = matchR[v];
                if (w == -1) reachable = true;
                else if (dist[w] == -1) {
                    dist[w] = dist[u] + 1;
                    q.push(w);
                }
            }
        }
        return reachable;
    }

    bool dfs(int u) {
        for (int v : adj[u]) {
            int w = matchR[v];
            if (w == -1 || (dist[w] == dist[u] + 1 && dfs(w))) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        dist[u] = -1;                // 避免重复访问
        return false;
    }

    int maxMatching() {
        matchL.assign(n, -1);
        matchR.assign(m, -1);
        dist.assign(n, -1);
        int res = 0;
        while (bfs()) {
            for (int u = 0; u < n; u++) {
                if (matchL[u] == -1 && dfs(u)) res++;
            }
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    HopcroftKarp hk(N, N);
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        hk.adj[u].push_back(v);
        hk.adj[v].push_back(u);
    }

    int matching = hk.maxMatching();
    ll ans = 1013LL * (2LL * N - matching);
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(M\sqrt{N})$（Hopcroft–Karp 最大匹配）
• 空间复杂度：$O(N + M)$