[NOIP2013] 货车运输

题目链接

洛谷

LOJ

题目分析

如果两座城市之间有多条路径可以相互到达，我们会选择路径中最小值最大的，其他较次的方案会被抛弃，最后得到的就是这张图的最大生成树。

得到最大生成树之后，对于任意一次查询，我们找一个点让这两个点都能到达，路径上的最小值即为答案。不难想到可以用 LCA 来实现，本题似乎不用倍增也能跑得很快，但我还是用的倍增。

对于求最大生成树，我用了 Prim 来实现。本题城市群之间可能不联通，在求 LCA 之前的 dfs 可以先进行染色，如果询问中的两座城市颜色不一样那就不联通。

代码实现

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

const int MAXN = 1000010;

struct Node {
    int id, dis, from;
};

struct Edge {
    int nxt;
    int to;
    int w;
    bool vis;
} edge[MAXN * 2];
priority_queue<Node> q;
int head[MAXN], cnt;
int N, M, Q;
int minn[MAXN][21];//minn[i][j]记录从i往上跳2^j个点的最大限重
int fa[MAXN][21], dep[MAXN];

namespace Prim
{
    int vis[MAXN];
}// namespace Prim

namespace LCA
{
    int col[MAXN];
    int cnt;
}// namespace LCA

bool operator<(const Node& a, const Node& b)
{
    return a.dis < b.dis;
}

void link(int u, int v, int w)
{
    edge[++cnt].nxt = head[u];
    edge[cnt].to = v;
    edge[cnt].w = w;
    head[u] = cnt;
}

void prim()
{
    for (int i = 1; i <= N; i++) {
        if (Prim::vis[i]) continue;
        q.push(Node{i, 0, 0});
        while (!q.empty()) {
            Node u = q.top();
            q.pop();
            if (Prim::vis[u.id]) continue;
            Prim::vis[u.id] = 1;

            edge[u.from].vis = 1;                    //记录该边属于最大生成树
            if (u.from & 1) {
                edge[u.from + 1].vis = 1;
            } else {
                edge[u.from - 1].vis = 1;
            } //双向边

            for (int i = head[u.id]; i; i = edge[i].nxt) {
                int to = edge[i].to;
                int w = edge[i].w;
                int from = i;
                if (Prim::vis[to]) continue;
                q.push(Node{to, w, from});
            }
        }
    }
}

void dfs(int x, int father, int w, int col)
{
    if (LCA::col[x]) return;
    LCA::col[x] = col;//染色
    fa[x][0] = father;
    minn[x][0] = w;//到父节点的minn就是到父节点的边的长度
    dep[x] = dep[father] + 1;
    for (int i = 1; (1 << i) <= dep[x]; i++) {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
        minn[x][i] = min(minn[x][i - 1], minn[fa[x][i - 1]][i - 1]);//倍增求最小边长
    }
    for (int i = head[x]; i; i = edge[i].nxt) {
        int to = edge[i].to;
        int cw = edge[i].w;
        if (to == father) continue;
        if (!edge[i].vis) continue;//必须是最大生成树上有的边
        dfs(to, x, cw, col);
    }
}

int getlca(int a, int b)
{
    if (LCA::col[a] != LCA::col[b]) return -1;
    int ans = 0x7fffffff;
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = 20; i >= 0; i--) {
        if (dep[a] - (1 << i) >= dep[b]) {
            ans = min(ans, minn[a][i]);
            a = fa[a][i];
        }
    }
    if (a == b) return ans;
    for (int i = 20; i >= 0; i--) {
        if (fa[a][i] == fa[b][i]) continue;

        ans = min(ans, min(minn[a][i], minn[b][i]));
        a = fa[a][i], b = fa[b][i];
    }
    return min(ans, min(minn[a][0], minn[b][0]));
}

int main()
{
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        link(u, v, w);
        link(v, u, w);
    }
    //使用prim求最大生成树
    prim();

    cin >> Q;
    //倍增LCA
    memset(minn, 0x3f, sizeof(minn));
    for (int i = 1; i <= N; i++) {
        dfs(i, 0, 0, ++LCA::cnt);
    }
    for (int i = 1; i <= Q; i++) {
        int a, b;
        cin >> a >> b;
        cout << getlca(a, b) << endl;
    }

    return 0;
}