[ICPC 2021 Macao R] Link-Cut Tree

题意

给一张无向图，第 i 条边的长度是 $2^i$ 。

要求找一个总长度最小的简单环。如果存在，就输出这个环包含哪些边的编号；如果不存在，输出 -1。

思路

先看一个只适合很小数据的暴力：

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143// brute.cpp：小图枚举所有边集，按简单环定义直接检查。
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v;
} edges[25];

int T;
int n, m;
int deg[20];
bool used_vertex[20];
vector<int> graph[20];

unsigned long long best_value;
vector<int> best_edges;

bool is_simple_cycle(int mask, vector<int> &picked_edges) {
    for (int i = 1; i <= n; i++) {
        deg[i] = 0;
        used_vertex[i] = false;
        graph[i].clear();
    }

    picked_edges.clear();

    for (int i = 1; i <= m; i++) {
        if (((mask >> (i - 1)) & 1) == 0) {
            continue;
        }
        int u = edges[i].u;
        int v = edges[i].v;
        deg[u]++;
        deg[v]++;
        used_vertex[u] = true;
        used_vertex[v] = true;
        graph[u].push_back(v);
        graph[v].push_back(u);
        picked_edges.push_back(i);
    }

    int vertex_cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!used_vertex[i]) {
            continue;
        }
        vertex_cnt++;
        if (deg[i] != 2) {
            return false;
        }
    }

    if (vertex_cnt < 3) {
        return false;
    }
    if ((int)picked_edges.size() != vertex_cnt) {
        return false;
    }

    queue<int> q;
    bool vis[20] = {false};
    int start = 0;
    for (int i = 1; i <= n; i++) {
        if (used_vertex[i]) {
            start = i;
            break;
        }
    }

    q.push(start);
    vis[start] = true;
    int reached = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        reached++;

        for (int v : graph[u]) {
            if (vis[v]) {
                continue;
            }
            vis[v] = true;
            q.push(v);
        }
    }

    return reached == vertex_cnt;
}

void solve_one_case() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edges[i].u >> edges[i].v;
    }

    best_value = numeric_limits<unsigned long long>::max();
    best_edges.clear();

    vector<int> picked_edges;
    int total_mask = 1 << m;
    for (int mask = 0; mask < total_mask; mask++) {
        if (!is_simple_cycle(mask, picked_edges)) {
            continue;
        }

        unsigned long long value = 0;
        for (int id : picked_edges) {
            value += (1ULL << id);
        }

        if (value < best_value) {
            best_value = value;
            best_edges = picked_edges;
        }
    }

    if (best_edges.empty()) {
        cout << -1 << '\n';
        return;
    }

    sort(best_edges.begin(), best_edges.end());
    for (int i = 0; i < (int)best_edges.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << best_edges[i];
    }
    cout << '\n';
}

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

    cin >> T;
    while (T--) {
        solve_one_case();
    }

    return 0;
}

暴力直接枚举边集，然后按简单环的定义去检查：

用到的点都必须度数为 2
连通
边数等于点数

这个写法最贴定义，但边稍微一多就完全跑不动。

这题真正关键的是边权形式：第 i 条边权是 $2^i$ 。

因为：

$2^i > 2^1 + 2^2 + ... + 2^{i-1}$

所以比较两个环大小时，决定性因素一定是“最大的那条边编号是谁”：

只要一个环的最大边编号更小，它的总长度就一定更小

于是最优环一定满足：

它的最大边编号尽可能小
在这个前提下，其它边怎么选再讨论

这就变成了一个 Kruskal 式的过程：

按边编号从小到大加边
在第一次遇到“这条边两端已经连通”的时候，就说明第一次出现了环

为什么这条边一定属于答案？

因为在它之前，图里还没有任何环；而一旦它加入形成了第一个环，这个环的最大边编号就是当前编号，已经是全局最小可能值。

更进一步，在这之前图一定是一片森林。

所以当前边 (u, v) 的两个端点在森林里有且仅有一条简单路径。把这条路径和当前边拼起来，就是唯一候选环，也就是答案。

实现上分两步：

用并查集在线判断第一条成环边是谁
只把它之前的边当成森林存下来，最后在森林里找 u 到 v 的唯一路径

代码

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143#include <bits/stdc++.h>
using namespace std;

const int MAXN = 400005;
const int MAXM = 800005;

int T;
int n, m;

int fa[MAXN];
int head[MAXN], to[MAXM], nxt[MAXM], edge_id[MAXM], edge_cnt;
int parent_node[MAXN], parent_edge[MAXN];
bool vis[MAXN];

void init_graph(int n) {
    edge_cnt = 0;
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        head[i] = 0;
    }
}

int find_root(int x) {
    if (fa[x] == x) {
        return x;
    }
    fa[x] = find_root(fa[x]);
    return fa[x];
}

void unite(int x, int y) {
    x = find_root(x);
    y = find_root(y);
    if (x != y) {
        fa[x] = y;
    }
}

void add_edge(int u, int v, int id) {
    edge_cnt++;
    to[edge_cnt] = v;
    edge_id[edge_cnt] = id;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

vector<int> find_path_edges(int start, int target) {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        vis[i] = false;
        parent_node[i] = 0;
        parent_edge[i] = 0;
    }

    q.push(start);
    vis[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u == target) {
            break;
        }

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (vis[v]) {
                continue;
            }
            vis[v] = true;
            parent_node[v] = u;
            parent_edge[v] = edge_id[i];
            q.push(v);
        }
    }

    vector<int> path_edges;
    int cur = target;
    while (cur != start) {
        path_edges.push_back(parent_edge[cur]);
        cur = parent_node[cur];
    }
    return path_edges;
}

void solve_one_case() {
    cin >> n >> m;
    init_graph(n);

    int cycle_u = 0;
    int cycle_v = 0;
    int cycle_edge = 0;

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;

        if (cycle_edge != 0) {
            continue;
        }

        if (find_root(u) == find_root(v)) {
            cycle_u = u;
            cycle_v = v;
            cycle_edge = i;
            continue;
        }

        unite(u, v);
        add_edge(u, v, i);
        add_edge(v, u, i);
    }

    if (cycle_edge == 0) {
        cout << -1 << '\n';
        return;
    }

    vector<int> answer = find_path_edges(cycle_u, cycle_v);
    answer.push_back(cycle_edge);
    sort(answer.begin(), answer.end());

    for (int i = 0; i < (int)answer.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << answer[i];
    }
    cout << '\n';
}

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

    cin >> T;
    while (T--) {
        solve_one_case();
    }

    return 0;
}

复杂度

设一组数据有 n 个点、m 条边。

并查集扫边： $O(m \alpha(n))$
在森林里找一次路径： $O(n)$

总复杂度可以看成 $O(m \alpha(n) + n)$ 。

空间复杂度 $O(n)$ 。

总结

这题表面在找最小环，真正用到的却是“边权按 $2^i$ 爆炸增长”这个性质。只要看出它等价于“先最小化最大边编号”，题目就会从最小环问题一下子降成“找到第一条成环边，再取森林唯一路径”。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[ICPC 2021 Macao R] Link-Cut Tree

目录

题意

思路

代码

复杂度

总结

一图流解析