城市环路

题目解析

基环树上的最大独立集问题

这个题目和 Missing problem: luogu/P2607 差不多

这个题目的难点不再于代码, 而是人类的大脑不擅长同时思考思考太多的东西(图上的点),现在我来带你一步一步思考:

取环上的任意一条边 $(u,v)$ , 显然最最终的答案里面, $u,v$ 两个点不能同时出现
设第 $i$ 合法的独立集合为 $d_i$
显然我们可以把所有的独立集组成的集合 $A = \{d_1,d_2,\cdots , d_n\}$ , 分成,不重不漏的三个集合
1. $B(u) =\{ d_i | u \in d_i \}$ 含有 $u$ 的独立集组成的集合
2. $B(v) = \{d_i | v \in d_i \}$ 含有 $v $ 的独立集组成的集合
3. $C = \{d_i | v \notin d_i \land u \notin d_i \}$
显然 $A = B(u) \cup B(v) \cup C$ (我觉得整个题目的核心就在这里!!!,理解这个就能理解整个题目)
进一步的,可以想到(为了减小写代码的量), 根据补集的思想
1. $\overline {B(u)} = B(v) \cup C = \{d_i | u \notin d_i \}$ ,表示不含有 $u$ 的集合
2. $\overline {B(v)} = B(u) \cup C= \{d_i | v \notin d_i \}$ ,表示不含有 $v$ 的集合

digraph G {
    rankdir=TB;
    node [shape=ellipse, style=filled];
    edge [dir=none];
    
    // 全集 A
    A [label="A\n所有独立集的集合", fillcolor=lightblue, shape=doublecircle];
    
    // 三个子集
    B_u [label="B(u)\n包含u的独立集", fillcolor=yellow];
    B_v [label="B(v)\n包含v的独立集", fillcolor=orange];
    C [label="C\n既不包含u也不包含v的独立集", fillcolor=lightgreen];
    
    // 补集
    not_B_u [label="¬B(u)\n不包含u的独立集", fillcolor=yellow, style="filled,dashed"];
    not_B_v [label="¬B(v)\n不包含v的独立集", fillcolor=orange, style="filled,dashed"];
    
    // 全集分解
    A -> B_u;
    A -> B_v;
    A -> C;
    
    // 补集关系
    not_B_u -> B_v [label="∪", fontcolor=red];
    not_B_u -> C [label="∪", fontcolor=red];
    
    not_B_v -> B_u [label="∪", fontcolor=red];
    not_B_v -> C [label="∪", fontcolor=red];
    
    // 布局调整
    {rank=same; B_u; B_v; C}
    {rank=same; not_B_u; not_B_v}
}

那么不就得到了 : $A = \overline{B(u)} \cup \overline{B(v)}$

那么 $\max (A) = \max( \max(\overline{B(u)}) ,\max(\overline{B(u)}))$

哪怎么求 $\max(\overline{B(u)})$ 呢? 显然这表示不选 $u$ 的情况,

可以想到如果 $u$ 删除,那么

变成一个树 , 直接树上DP
图断可能开成两个连通分量:

下面的图有点问题: 不是删除边,是删除点

digraph G {
    rankdir=LR;
    subgraph cluster_case1 {
        label="情况1：删除边(u,v)后形成一棵树";
        style=dashed;
        
        node [shape=circle];
        u [label="u", fillcolor=yellow];
        v [label="v", fillcolor=orange];
        a [label="a"];
        b [label="b"];
        c [label="c"];
        u1 [label="u1"];
        v1 [label="v1"];
        
        // 树结构
        u -> a;
        a -> b;
        b -> c;
        c -> v;
        u -> u1;
        v -> v1;
        
        // 删除的边用虚线表示
        u -> v [style=dashed, color=gray, label="删除"];
    }
    
    subgraph cluster_case2 {
        label="情况2：删除边(u,v)后形成两个连通分量";
        style=dashed;
        
        node [shape=circle];
        u2 [label="u", fillcolor=yellow];
        v2 [label="v", fillcolor=orange];
        a2 [label="a"];
        b2 [label="b"];
        c2 [label="c"];
        u12 [label="u1"];
        v12 [label="v1"];
        
        // 第一个连通分量（包含u）
        subgraph cluster_comp1 {
            label="连通分量1";
            u2 -> a2;
            a2 -> b2;
            b2 -> c2;
            u2 -> u12;
        }
        
        // 第二个连通分量（包含v）
        subgraph cluster_comp2 {
            label="连通分量2";
            v2 -> v12;
        }
        
        // 删除的边用虚线连接两个分量
        u2 -> v2 [style=dashed, color=gray, label="删除", constraint=false];
    }
}

这个时候,可以虚拟的点,把两个部分,连接起来,形成一颗树,

digraph G {
    rankdir=TB;
    node [shape=circle];
    
    // 虚拟节点
    virtual [label="虚拟节点", shape=doublecircle, fillcolor=lightgray, style=filled];
    
    // 第一个连通分量（包含u）
    subgraph cluster_left {
        label="连通分量1（包含u）";
        style=dotted;
        
        u [label="u", fillcolor=yellow];
        a [label="a"];
        b [label="b"];
        u1 [label="u1"];
        
        u -> a;
        a -> b;
        u -> u1;
    }
    
    // 第二个连通分量（包含v）
    subgraph cluster_right {
        label="连通分量2（包含v）";
        style=dotted;
        
        v [label="v", fillcolor=orange];
        c [label="c"];
        v1 [label="v1"];
        
        v -> c;
        v -> v1;
    }
    
    // 虚拟节点连接两个分量
    virtual -> u [style=dashed, color=blue, label="连接"];
    virtual -> v [style=dashed, color=blue, label="连接"];
    
    // 说明
    note [label="虚拟节点：\n1. 不能被选中\n2. 连接两个连通分量\n3. 形成一棵树", shape=note, fillcolor=lightyellow, style=filled];
}

这个虚拟的点不能被选中, 那么就是求 $dp[u][0]$

本质: 最值集合拆分

怎么题目虚拟点 ?

最简单的方式,就是删除点 $u$ 在环上的一条边: 这样体现出来的虚拟的思想

Open in Excalidraw

代码

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
105
106
107
108
109
110
111
112
113/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-09 17:39:05
 */
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;

const int MAXN = 100005;

// 邻接表
vector<int> adj[MAXN];
int p[MAXN]; // 人流量
int n;
double k;

// DP 数组: dp[i][0] 不选, dp[i][1] 选
long long dp[MAXN][2]; 

// 记录环上的两个端点
int S, T;

// 并查集用于找环
struct DSU {
    int fa[MAXN];
    void init(int size) {
        for(int i=0; i<=size; i++) fa[i] = i;
    }
    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }
    bool merge(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            fa[fx] = fy;
            return true;
        }
        return false;
    }
} dsu;

// 树形DP函数
void dfs(int u, int fa) {
    dp[u][0] = 0;
    dp[u][1] = p[u];
    
    for (int v : adj[u]) {
        if (v == fa) continue; // 防止走回头路
        dfs(v, u);
        
        // 状态转移
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    
    dsu.init(n);
    
    // 读入边并处理基环
    for (int i = 0; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        // 如果 u和v 已经连通，说明这条边构成了环
        if (!dsu.merge(u, v)) {
            S = u;
            T = v;
            // !!! 关键点在这里 !!!
            // 发现这条边 (u, v) 会构成环，我们只记录端点 S=u, T=v
            // 注意：并没有执行 adj[u].push_back(v);
            // 这条边被物理上“丢弃”了，没有存入邻接表 adj 中
            // 相当于: 删除了 u 在环上的边
        } else {
            // 否则这是一条树边，加入邻接表
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }
    
    cin >> k;

    // 情况1：强制不选 S
    // 我们以 S 为根进行 DFS，最后取 dp[S][0]
    // 这里的 dp[S][0] 意味着 S 没被选，那么 T 选不选都无所谓，符合边(S,T)的约束
    memset(dp, 0, sizeof(dp));
    dfs(S, -1);
    long long ans1 = dp[S][0];
    
    // 情况2：强制不选 T
    // 我们以 T 为根进行 DFS，最后取 dp[T][0]
    memset(dp, 0, sizeof(dp));
    dfs(T, -1);
    long long ans2 = dp[T][0];
    
    // 结果计算
    double final_ans = max(ans1, ans2) * k;
    
    // 输出保留一位小数
    cout << fixed << std::setprecision(1) << final_ans << endl;

    return 0;
}

目录

题目解析

怎么题目虚拟点 ?

代码