题解：UVA1464 Traffic Real Time Query System

szh_AK_all · 2024-05-10 21:27:30 · 题解

双倍经验。

分析

首先考虑如何计算从一点至另一点必须经过的点的数量。

首先构建圆方树，显然，要计算的就是两点间割点的数量。由于在路径中，通常是一个方点通往一个圆点，再通往一个方点，所以割点的数量（包括该两点）即为 \lfloor \frac{x}{2} \rfloor+1，其中 x 为两点间的距离。

再考虑这道题目，由于是计算一边至另一边必须经过的点的数量，所以可以将边转换成点，计算点与点之间的割点的数量。由于该两点是不用计入答案的，所以割点的数量即为 \lfloor \frac{x}{2} \rfloor-1，其中 x 仍然表示两点间的距离。

如何将边转换成点呢？显然，每条边接着两个点，找出这两条边所连接的点两两组合的答案中的最大值即可。

要注意的细节就是本题是多测。

Code

#include <bits/stdc++.h>
using namespace std;
int dfn[1000005], low[1000005], cnt, in[1000005];
stack<int>st;
vector<int>g[1000005];
vector<int>s[1000005];
int SCC;
int xx[100005], yy[100005];

void dfs(int k) {
    cnt++;
    dfn[k] = cnt;
    low[k] = cnt;
    st.push(k);
    for (auto x : g[k]) {
        if (!dfn[x]) {
            dfs(x);
            low[k] = min(low[k], low[x]);
            if (low[x] >= dfn[k]) {
                SCC++;
                s[SCC].push_back(k);
                s[k].push_back(SCC);
                int t;
                do {
                    t = st.top();
                    st.pop();
                    s[SCC].push_back(t);
                    s[t].push_back(SCC);
                } while (t != x);
            }
        } else
            low[k] = min(low[k], dfn[x]);
    }
}
int de[1000005];
int fa[1000005][21];

void dfs1(int x, int f) {
    fa[x][0] = f;
    de[x] = de[f] + 1;
    for (int i = 1; i <= 20; i++)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (int i = 0; i < (int)(s[x].size()); i++) {
        int y = s[x][i];
        if (y != f)
            dfs1(y, x);
    }
}

int LCA(int x, int y) {
    if (de[x] < de[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--)
        if (de[fa[x][i]] >= de[y])
            x = fa[x][i];
    if (x == y)
        return x;
    for (int i = 20; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int zhi(int u, int v) {
    int ans = de[u] + de[v] - 2 * de[LCA(u, v)];
    return ans / 2 - 1;
}

int main() {
    while (1) {
        int n, m;
        cin >> n >> m;
        if (!n && !m)
            return 0;
        for (int i = 1; i <= m; i++) {
            int x, y;
            cin >> x >> y;
            xx[i] = x, yy[i] = y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        SCC = n;
        for (int i = 1; i <= n; i++)
            if (!dfn[i])
                dfs(i), st.pop();
        for (int i = 1; i <= n; i++)
            if (!de[i])
                dfs1(i, 0);
        int q;
        cin >> q;
        while (q--) {
            int u, v;
            cin >> u >> v;
            int ans = max(max(zhi(xx[u], xx[v]), zhi(xx[u], yy[v])), max(zhi(yy[u], xx[v]), zhi(yy[u], yy[v])));
            cout << ans << endl;
        }
        for (int i = 1; i <= 2 * n; i++) {
            g[i].clear();
            s[i].clear();
        }
        cnt = 0;
        memset(low, 0, sizeof(low));
        memset(dfn, 0, sizeof(dfn));
        memset(de, 0, sizeof(de));
        memset(fa, 0, sizeof(fa));
        while (st.size())
            st.pop();
    }
}