Skip to content

BZOJ - 1718. Redundant Paths

题解约 1.1 千字
# 洛谷 # BZOJ # 图论 # AcWing # USACO # 2006 # Tarjan
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

为了从 FF 个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树。

奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。

每对草场之间已经有至少一条路径。

给出所有 RR 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成。

两条路径相互分离，是指两条路径没有一条重合的道路。但是，两条分离的路径上可以有一些相同的草场。

对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。

#输入格式

第 11 行，两个用空格分隔的整数 FF 和 RR。

接下来 RR 行，每行输入两个整数，表示两个草场，它们之间有一条道路。

#输出格式

一行一个整数，表示最少的需要新建的道路数。

#输入输出样例

样例输入 #1

7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7

样例输出 #1

2

#数据范围与约定

对于 100%100\% 的数据，1≤F≤50001 \leq F \leq 5000，F<R≤10000F < R \leq 10000。

#思路

由题：

两条路径相互分离，是指两条路径没有一条重合的道路。

可知：

对于图中的任意两点 A,BA, B 之间的所有路径上，不能够存在一条边满足如果不经过它，就不能从点 AA 到达点 BB。

换言之，就是不能存在一条边使得删去它后整个图变得不连通。那么题目的要求就可以转化为：给定一个连通无向图，求出加边的最小数量使得整个图变为一个双连通分量。

先求出图中所有的双连通分量并缩点，缩点之后图就变成了一棵树的形状，那么只需要对这棵树加边，使其构成双连通分量即可。

对于树上的每一个叶子节点，如果将其与它父亲节点的连边删去，那么这个节点就会被孤立，无法构成双连通分量。所以将其与其他节点再连一条边即可避免发生这种情况，一个比较显然的结论就是将这条边连向另一个叶子节点是最优的。那么对于有偶数个叶子节点的树，需要连 cnt2\frac{\mathit{cnt}}{2} 个点，对于有奇数个叶子节点的树，需要连 cnt+12\frac{\mathit{cnt} + 1}{2} 个点。整理得 ⌊cnt+12⌋\lfloor \frac{\mathit{cnt} + 1}{2} \rfloor。

#代码

C++
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
#include <iostream>
#include <cstring>
#include <stack>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5005,
          M = 10005 << 1;

int f, r, ans;
int idx, head[N], edge[N], next[N];  // 链式前向星
int cnt, dfn[N], low[N];             // Tarjan 辅助数组
int dcc_cnt, siz[N], id[N], in[N];   // 双连通分量
bool bridge[N];                      // 桥边
std::stack<int> st;

void add(int u, int v) {
    next[idx] = head[u];
    edge[idx] = v;
    head[u] = idx++;
}

// Tarjan 求双连通分量
void tarjan(int u, int in_edge) {
    dfn[u] = low[u] = ++cnt;
    st.push(u);

    for (int i = head[u]; ~i; i = next[i]) {
        int v = edge[i];

        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = std::min(low[u], low[v]);

            if (dfn[u] < low[v]) {
                bridge[i] = bridge[i ^ 1] = true;
            }
        } else if (i != (in_edge ^ 1)) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        dcc_cnt++;
        int v;
        do {
            v = st.top();
            st.pop();
            id[v] = dcc_cnt;
            siz[dcc_cnt]++;
        } while (v != u);
    }
}

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

    memset(head, 0xff, sizeof(head));

    cin >> f >> r;

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

        add(u, v);
        add(v, u);
    }

    tarjan(1, -1);

    for (int i = 0; i < idx; i++) {
        if (bridge[i]) {
            in[id[edge[i]]]++;
        }
    }

    for (int i = 1; i <= dcc_cnt; i++) {
        if (in[i] == 1) ans++;
    }

    cout << (ans + 1) / 2 << endl;

    return 0;
}