Skip to content

BZOJ - 1718. Redundant Paths

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

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

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

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

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

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

#输入格式

11 行,两个用空格分隔的整数 FFRR

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

#输出格式

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

#输入输出样例

样例输入 #1

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

样例输出 #1

2

#数据范围与约定

对于 100%100\% 的数据,1F50001 \leq F \leq 5000F<R10000F < 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

#代码

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;
}