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

代码

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