「一本通 5.2 练习 5」骑士

形式化题目

给定一个包含 $N$ 个顶点的有向图，每个顶点 $i$ 有一个正整数点权 $v_i$ 以及唯一的一条有向出边 $i \to h_i$ （ $h_i \neq i$ ）。

如果视所有的有向边为无向边，求该图的一个最大权独立集：选出一个顶点子集 $S$ ，使得对于图中的任意边 $(u, v)$ ， $u$ 和 $v$ 不同时属于 $S$ ，且 $\sum_{u \in S} v_u$ 最大。

正解

思路

1. 问题建模与图的结构

每个骑士 $i$ 厌恶 $h_i$ ，即 $i$ 与 $h_i$ 之间不能同时被选入军团。在无向图的角度，这对应一条无向边 $(i, h_i)$ 。我们要选出一个点集，任意两点之间没有边相连，且点权和最大——这是经典的最大权独立集问题。

一般图的最大权独立集是 NP-hard 的，但本题给出的图具有特殊结构：每个顶点恰有一条出边，因此在无向图意义下，每个连通块的边数等于顶点数（ $|V| = |E|$ ）。这样的连通块称为基环树（内向基环树），整张图是由若干个基环树组成的基环树森林。不同连通块之间相互独立，总的最大战斗力等于各个连通块最大权独立集之和。

2. 拓扑排序剪枝：收缩树枝

对于单一基环树连通块，它由一个核心的“简单环”以及挂在环上若干节点的“外向树枝”构成。

由于有向边是 $i \to h_i$ （从树枝指向环），所有叶子节点的入度为 $0$ 。我们可以仿照拓扑排序（Kahn 算法）自底向上剥除所有树枝节点：

设 $f_0[u]$ 表示不选节点 $u$ 时， $u$ 子树内的最大点权和； $f_1[u]$ 表示选节点 $u$ 时， $u$ 子树内的最大点权和。初始 $f_0[u] = 0, f_1[u] = v_u$ 。
将所有入度为 $0$ 的节点加入队列；
每次取出队首节点 $u$ ，转移给它的唯一出边邻居 $p = h_i$ ：
$f_0[p] \leftarrow f_0[p] + \max(f_0[u], f_1[u])$

$f_1[p] \leftarrow f_1[p] + f_0[u]$
将 $p$ 的入度减 $1$ 。若 $p$ 的入度变为 $0$ ，则将其加入队列继续剪枝。

当拓扑排序结束时：

所有树枝上的节点均已完成树形 DP 并被移除；
剩下的入度大于 $0$ 的节点恰好构成该连通块的唯一简单环；
环上每个节点 $u$ 的 $f_0[u]$ 和 $f_1[u]$ 已经包含了挂在它上面的整棵树枝的最优贡献。

3. 破环为链：环上的两次 DP

设环上的节点按拓扑出边顺序依次为 $c_0, c_1, \dots, c_{k-1}$ ，由于存在边 $(c_{k-1}, c_0)$ ， $c_0$ 与 $c_{k-1}$ 不能同时选。我们通过枚举 $c_0$ 的取舍破除环的环形后效性：

方案 1：强制不选 $c_0$
- 初始化： $dp_0 = f_0[c_0], dp_1 = -\infty$ ；
- 沿环递推 $i = 1, \dots, k-1$ ：
  $dp'_0 = \max(dp_0, dp_1) + f_0[c_i]$
  
  $dp'_1 = dp_0 + f_1[c_i]$
- 递推结束后，由于 $c_0$ 未选， $c_{k-1}$ 可选可不选，该方案的最优值为 $\max(dp_0, dp_1)$ 。
方案 2：强制选 $c_0$
- 初始化： $dp_0 = -\infty, dp_1 = f_1[c_0]$ ；
- 沿环同样规则递推到 $c_{k-1}$ ；
- 递推结束后，由于 $c_0$ 已经被选， $c_{k-1}$ 绝对不能选，故该方案的最优值为 $dp_0$ 。

该环连通块的最大权独立集即为 $\max(\text{方案1最优值}, \text{方案2最优值})$ 。遍历所有连通块将结果累加，即可得到全局答案。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-04-19 10:00
# update_at: 2026-04-19 10:00

import sys

NEG_INF = -10**18  # 强制不选或非法状态的惩罚权值


def trim_trees(n: int, val: list[int], to: list[int], deg: list[int]) -> tuple[list[int], list[int]]:
    """用拓扑排序把基环树外向树枝收缩到环上节点，返回每个节点的 (f0, f1) 权值。"""
    f0 = [0] * (n + 1)
    f1 = val[:]
    queue = [u for u in range(1, n + 1) if deg[u] == 0]
    head = 0

    while head < len(queue):
        u = queue[head]
        head += 1
        p = to[u]
        f0[p] += max(f0[u], f1[u])
        f1[p] += f0[u]
        deg[p] -= 1
        if deg[p] == 0:
            queue.append(p)

    return f0, f1


def solve_cycle(cycle: list[int], f0: list[int], f1: list[int]) -> int:
    """在单个环上做破环 DP，返回该基环树连通块的最大权独立集。"""
    # 方案 1: cycle[0] 强制不选
    dp0, dp1 = f0[cycle[0]], NEG_INF
    for u in cycle[1:]:
        dp0, dp1 = max(dp0, dp1) + f0[u], dp0 + f1[u]
    best_without_root = max(dp0, dp1)

    # 方案 2: cycle[0] 强制选，则 cycle[-1] 强制不选
    dp0, dp1 = NEG_INF, f1[cycle[0]]
    for u in cycle[1:]:
        dp0, dp1 = max(dp0, dp1) + f0[u], dp0 + f1[u]
    best_with_root = dp0

    return max(best_without_root, best_with_root)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        n = next(data)
    except StopIteration:
        return

    val = [0] * (n + 1)
    to = [0] * (n + 1)
    deg = [0] * (n + 1)

    for i in range(1, n + 1):
        val[i] = next(data)
        h = next(data)
        to[i] = h
        deg[h] += 1

    f0, f1 = trim_trees(n, val, to, deg)

    ans = 0
    vis = [False] * (n + 1)
    for i in range(1, n + 1):
        if deg[i] > 0 and not vis[i]:
            cycle: list[int] = []
            curr = i
            while not vis[curr]:
                vis[curr] = True
                cycle.append(curr)
                curr = to[curr]
            ans += solve_cycle(cycle, f0, f1)

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 10:11
 * update_at: 2026-10-05 10:11
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 5;

// 骑士编号 1..n，每个骑士恰好厌恶一个人，形成基环树森林
int val[MAXN];    // val[u]: 骑士 u 的战斗力
int to_[MAXN];    // to_[u]: u 最厌恶的骑士（u 有一条指向它的出边）
int deg[MAXN];    // deg[u]: u 的入度，拓扑排序剥叶子用
ll f0[MAXN];      // f0[u]: 不选 u 时，u 子树（含收缩贡献）内的最大权和
ll f1[MAXN];      // f1[u]: 选 u 时，u 子树（含收缩贡献）内的最大权和
int que[MAXN];    // 手写队列：拓扑排序中入度为 0 的节点
bool vis[MAXN];   // vis[u]: u 是否已属于某个处理过的环
int cyc[MAXN];    // 环上节点的收集数组

// 拓扑排序剥除所有树枝：树枝上的树形 DP 收缩到环上节点
// 返回剩余入度 > 0 的节点个数（即所有环上的节点数）
int trim_trees(int n) {
    int head = 0, tail = 0;
    for (int u = 1; u <= n; ++u)
        if (deg[u] == 0) que[tail++] = u;
    while (head < tail) {
        int u = que[head++];
        int p = to_[u];
        // 树枝贡献转移给唯一出边邻居 p（与经典树形 DP 一致）
        f0[p] += max(f0[u], f1[u]);
        f1[p] += f0[u];
        if (--deg[p] == 0) que[tail++] = p;
    }
    return n - tail; // 未入过队的节点入度仍 > 0，正好是环上节点
}

// 在环上破环为链做 DP，返回该基环树的最大权独立集
ll solve_cycle(int m) {
    const ll NEG = -(1LL << 60);

    // 方案 1：强制不选环首 cyc[0]，则环尾可选可不选
    ll dp0 = f0[cyc[0]], dp1 = NEG;
    for (int i = 1; i < m; ++i) {
        int u = cyc[i];
        ll nd0 = max(dp0, dp1) + f0[u];
        ll nd1 = dp0 + f1[u];
        dp0 = nd0;
        dp1 = nd1;
    }
    ll best1 = max(dp0, dp1);

    // 方案 2：强制选环首 cyc[0]，则环尾强制不选
    dp0 = NEG;
    dp1 = f1[cyc[0]];
    for (int i = 1; i < m; ++i) {
        int u = cyc[i];
        ll nd0 = max(dp0, dp1) + f0[u];
        ll nd1 = dp0 + f1[u];
        dp0 = nd0;
        dp1 = nd1;
    }
    ll best2 = dp0;

    return max(best1, best2);
}

int main() {
    // 关闭同步，N 最大 1e6，必须快读快写
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;
    for (int u = 1; u <= n; ++u) {
        cin >> val[u] >> to_[u];
        f1[u] = val[u]; // 初始树形 DP：选自己至少有自身权值
        deg[to_[u]]++;
    }

    trim_trees(n);

    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (deg[i] > 0 && !vis[i]) {
            // 沿出边走一圈收集环上节点
            int m = 0;
            int u = i;
            while (!vis[u]) {
                vis[u] = true;
                cyc[m++] = u;
                u = to_[u];
            }
            ans += solve_cycle(m);
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(N)$ 。每个节点在拓扑排序中入队与出队至多一次；所有环上的节点被遍历两次用于破环 DP，常数极小，能在线性时间内快速处理 $N = 10^6$ 。
空间复杂度： $\mathcal{O}(N)$ 。需要存储图的指向数组、度数数组及 DP 状态数组，占用线性内存。

总结

基环树标准套路：对于每个点恰好一条出边的函数图（基环树森林），利用拓扑排序“剥叶子”可以在避免显式建反向邻接表的同时，自然地完成外向树枝的自底向上树形 DP。
破环为链：环上的冲突限制只需针对一个关键基准点讨论其“选”与“不选”两种互斥状态，即可彻底拆解环的循环依赖，退化为两遍标准的线性序列 DP。

图示解析

这张图展示了基环树最大权独立集的求解脉络：

text

1
2
3
4
5
6
7
8基环树森林 (每个节点一条出边)
|- 拓扑排序剪枝
|  `- 从入度为 0 的叶子自底向上做树形 DP
|     `- 树枝贡献完全收缩到环上节点 (f0, f1)
`- 环上破环两次 DP
   |- 方案 1: 强制不选起点 c0 -> 终点 ck-1 可选可不选
   |- 方案 2: 强制选起点 c0   -> 终点 ck-1 强制不选
   `- 取两方案较大值，累加每个连通块的答案

样例 1 结构示意

输入数据构建的关系如下： $1 \to 2$ （1 厌恶 2）， $2 \to 3$ （2 厌恶 3）， $3 \to 1$ （3 厌恶 1）。三个节点构成一个长度为 3 的简单环：

graph LR
    1((1: 权值10)) --> 2((2: 权值20))
    2 --> 3((3: 权值30))
    3 --> 1

若选 3，则 1 和 2 均不能选，收益为 30；
若选 2，则 3 和 1 均不能选，收益为 20；
若选 1，则 2 和 3 均不能选，收益为 10；最优解为选 3，最大战斗力为 30。