[POI 2008] BLO-Blockade

GitHub跳转原题关系图返回列表

封锁一个点后，真正新增损失来自它把图切成的多个连通块；用 Tarjan 求割点时顺手统计每个被切下来的子树大小，就能在线性时间算出每个点造成的访问损失。

OJ: luogu

题目 ID: P3469

难度:提高+/省选-

标签:图论tarjan割点

日期: 2026-06-20 02:28

目录

  1. 题意
    1. 样例图
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

有一张连通无向图，每个点代表一个城镇，每个城镇里正好有一个居民。

原本一共应该发生：

  • n * (n - 1) 次访问

因为每个人都想访问其他所有人一次。

现在如果封锁某个城镇 u，就会导致：

  • 任何和 u 有关的访问都不可能发生
  • 删掉 u 以后，如果图被分成多个连通块，不同连通块之间的人也无法互相访问

题目要求对每个点 u 输出：

  • 如果封锁 u，最终有多少次访问无法进行

样例图

样例图长这样：

graph G {
  1 -- 2;
  1 -- 3;
  2 -- 3;
  3 -- 4;
  4 -- 5;
}

从图上就能看出：

  • 点 3 和点 4 是关键位置
  • 封锁 3 时，图会裂成 {1,2} 和 {4,5}
  • 封锁 4 时，图会裂成 {1,2,3} 和 {5}

所以这两个点的答案会比普通点更大。

思路

先看一个最直接的暴力：

cpp
// brute.cpp：枚举封锁哪个点，直接数删点后的连通块大小。
// 各块之间的访问全部作废，再加上所有“和被封锁点有关”的访问，就是答案。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, m;
vector<int> g[MAXN];
bool vis[MAXN];

void dfs(int u, int ban, int &cnt) {
    vis[u] = true;
    cnt++;

    for (size_t i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == ban || vis[v]) {
            continue;
        }
        dfs(v, ban, cnt);
    }
}

long long calc(int ban) {
    for (int i = 1; i <= n; i++) {
        vis[i] = false;
    }

    vector<int> comps;
    for (int i = 1; i <= n; i++) {
        if (i == ban || vis[i]) {
            continue;
        }
        int sz = 0;
        dfs(i, ban, sz);
        comps.push_back(sz);
    }

    long long bad = 2LL * (n - 1);
    for (size_t i = 0; i < comps.size(); i++) {
        for (size_t j = i + 1; j < comps.size(); j++) {
            bad += 2LL * comps[i] * comps[j];
        }
    }
    return bad;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
    }

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        cout << calc(i) << '\n';
    }

    return 0;
}

暴力做法是：

  1. 枚举封锁哪个点 u
  2. 真的把 u 删掉
  3. 重新数删点后的每个连通块大小
  4. 统计不同连通块之间一共有多少对访问作废

这个方法容易理解，但每个点都重跑一遍 DFS，复杂度太高。

正式做法的关键是把答案拆成两部分：

  1. 所有和 u 直接有关的访问
    这部分固定是 2 * (n - 1)
    因为别人去 u、以及 u 去别人，这两类访问都作废。

  2. 删掉 u 以后，不同连通块之间的访问
    这部分只有当 u 是割点时才会额外出现。

所以问题就变成：

  • 删掉点 u 后，会分出哪些连通块？它们大小是多少？

这正是 Tarjan 割点里 low[v] >= dfn[u] 的含义。

如果 u 有一个儿子 v 满足：

low[v] >= dfn[u]

说明删掉 u 以后，v 这棵子树会单独裂成一个连通块，大小就是 sub_size[v]。

于是我们在 DFS 回溯时，把每个这样的“被切下来的块”依次拿出来计数即可。

设这些块的大小依次是：

  • c1, c2, ..., ck

那么它们和“前面已经切出来的点”之间会新增：

  • 2 * c_i * (前面所有块大小之和)

次作废访问。

最后还要补上一个“剩余大块”：

  • 它的大小是 n - 1 - (c1 + c2 + ... + ck)

这块和前面所有被切下来的块之间，也会产生同样的双向损失。

所以整道题其实就是：

  • Tarjan 求割点
  • 同时维护每棵子树大小
  • 在回溯时用这些大小直接算贡献

代码

cpp
#include <bits/stdc++.h>
using namespace std;

struct Frame {
    int u;          // 当前点
    int iter_edge;  // 当前枚举到哪条边
};

int n, m;
vector<int> head, to, nxt;
int edge_cnt;

vector<int> dfn, low, parent_node, parent_edge;
vector<int> sub_size, child_cnt;
vector<long long> cut_sum, answer;
int dfs_clock;

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

// 非递归 Tarjan 求割点相关贡献。
// answer[u] 统计“封锁 u 以后，无法发生的有序访问次数”。
void solve_component(int start) {
    vector<Frame> st;

    st.push_back({start, head[start]});
    parent_node[start] = 0;
    parent_edge[start] = 0;

    dfn[start] = low[start] = ++dfs_clock;
    sub_size[start] = 1;
    child_cnt[start] = 0;
    cut_sum[start] = 0;
    answer[start] = 2LL * (n - 1);

    while (!st.empty()) {
        Frame &cur = st.back();
        int u = cur.u;

        if (cur.iter_edge != 0) {
            int e = cur.iter_edge;
            cur.iter_edge = nxt[e];
            int v = to[e];

            if (e == (parent_edge[u] ^ 1)) {
                continue;
            }

            if (!dfn[v]) {
                parent_node[v] = u;
                parent_edge[v] = e;
                child_cnt[u]++;

                dfn[v] = low[v] = ++dfs_clock;
                sub_size[v] = 1;
                child_cnt[v] = 0;
                cut_sum[v] = 0;
                answer[v] = 2LL * (n - 1);

                st.push_back({v, head[v]});
                continue;
            }

            if (dfn[v] < dfn[u]) {
                low[u] = min(low[u], dfn[v]);
            }
            continue;
        }

        st.pop_back();

        // u 的所有儿子都处理完了，现在把“剩余那个大块”的贡献补上。
        answer[u] += 2LL * cut_sum[u] * (n - 1 - cut_sum[u]);

        if (parent_node[u] != 0) {
            int p = parent_node[u];
            sub_size[p] += sub_size[u];
            low[p] = min(low[p], low[u]);

            // 删除 p 后，u 子树会单独裂成一个连通块。
            if (low[u] >= dfn[p]) {
                answer[p] += 2LL * cut_sum[p] * sub_size[u];
                cut_sum[p] += sub_size[u];
            }
        }
    }
}

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

    cin >> n >> m;

    head.assign(n + 1, 0);
    to.assign(2 * m + 5, 0);
    nxt.assign(2 * m + 5, 0);
    edge_cnt = 1;

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

    dfn.assign(n + 1, 0);
    low.assign(n + 1, 0);
    parent_node.assign(n + 1, 0);
    parent_edge.assign(n + 1, 0);
    sub_size.assign(n + 1, 0);
    child_cnt.assign(n + 1, 0);
    cut_sum.assign(n + 1, 0);
    answer.assign(n + 1, 0);
    dfs_clock = 0;

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            solve_component(i);
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

复杂度

每个点访问一次，每条边只会被常数次处理，所以：

  • 时间复杂度 O(n+m)O(n+m)
  • 空间复杂度 O(n+m)O(n+m)

总结

这题最重要的转化是：

  • 不要直接去算“还能访问多少次”
  • 而是去算“哪些访问作废了”

一旦改成“作废访问数”，就会自然拆成：

  1. 和被封锁点本身有关的固定损失
  2. 割点把图切开后，不同块之间的额外损失

于是 Tarjan 的 low[v] >= dfn[u] 不再只是“判割点”，而是直接告诉我们：

  • 有一个大小为 sub_size[v] 的连通块被切下来了

这就是这题的核心。

一图流解析

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

一图流解析