P1967 [NOIP2013 提高组] 货车运输题解

2024-04-02 12:32 由 gctiruct 发表于 #其他

P1967 [NOIP2013 提高组] 货车运输

思路：

由于题目要求的是使两点之间的最小边权最大，所以可以构造最大生成树（最大生成树一定是最大瓶颈生成树，而瓶颈生成树上两点之间的路径，在原图中的所有路径中，最小边权仍然最大，即满足题目要求，详见 https://oi-wiki.org/graph/mst/#性质），答案为最大生成树上的路径的最小边权。

求树上路径上的边权最值可以使用 \(LCA\)，因为它可以通过合并两个点的 \(LCA\) 和这两个点到 \(LCA\) 的路径的边权最值得来。

做法：

先用 \(Kruskal\) 算出最大生成树，再用倍增的方式计算 \(LCA\)，并维护每条路径上的最小边权。

\(e\) 表示初始图，\(G\) 表示最大生成树，\(deep\) 表示点的深度，\(fa_{i,j}\) 表示 \(i\) 的第 \(2^j\) 级祖先，\(w_{i,j}\) 表示 \(i\) 到 \(i\) 的第 \(2^j\) 级祖先的路径上的最小边权，在求 \(LCA\) 的过程中输出经过的点上的最小边权即可。

代码：

时间复杂度：\(\Theta(m\log m + n\log n)\)

#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;

const int N = 10010;
const int E = 50010;
const int M = 25;
const int INF = 1e18;

struct Node { int v, w; } ;
struct Edge { int u, v, w; } ;

int n, m, q;
int f[N], fa[N][M], deep[N], w[N][M];
bool vis[N];
Edge e[E];
vector<Node> G[N];

// 排序初始边，用于求最大生成树
bool cmpk(Edge x, Edge y) { return x.w > y.w; } 

int find(int x) // 并查集 - 查找祖先
{
    if(f[x] == x)
        return f[x];
    return f[x] = find(f[x]);
}

void kruskal() // 求最大生成树
{
    sort(e+1, e+m+1, cmpk);
    for(int i=1; i<=n; i++)
        f[i] = i;
    for(int i=1; i<=m; i++)
    {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if(find(u) == find(v))
            continue;
        f[find(u)] = find(v);
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
}

void predfs(int u) // LCA初始化1 - 求出深度、父亲
{
    vis[u] = true;
    for(int i=0; i<G[u].size(); i++)
    {
        int v = G[u][i].v;
        if(vis[v])
            continue;
        deep[v] = deep[u] + 1;
        fa[v][0] = u;
        w[v][0] = G[u][i].w;
        predfs(v);
    }
}

int LCA(int x, int y) // 求LCA和答案
{
    if(find(x) != find(y))
        return -1;
    int ans = INF;
    if(deep[x] > deep[y])
        swap(x, y);
    for(int i=20; i>=0; i--)
    {
        if(deep[fa[y][i]] < deep[x])
            continue;
        ans = min(ans, w[y][i]);
        y = fa[y][i];
    }
    if(x == y)
        return ans;
    for(int i=20; i>=0; i--)
    {
        if(fa[x][i] == fa[y][i])
            continue;
        ans = min(ans, min(w[x][i], w[y][i]));
        x = fa[x][i];
        y = fa[y][i];
    }
    ans = min(ans, min(w[x][0], w[y][0]));
    return ans;
}

void prelca() // LCA初始化2 - 求出祖先
{
    for(int i=1; i<=20; i++)
    {
        for(int j=1; j<=n; j++)
        {
            fa[j][i] = fa[fa[j][i-1]][i-1];
            w[j][i] = min(w[j][i-1], w[fa[j][i-1]][i-1]);
        }
    }
}

signed main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    kruskal();
    for(int i=1; i<=n; i++)
    {
        if(vis[i])
            continue;
        deep[i] = 1;
        predfs(i);
        fa[i][0] = i;
        w[i][0] = INF;
    }
    prelca();
    cin >> q;
    while(q --)
    {
        int x, y; cin >> x >> y;
        cout << LCA(x, y) << '\n';
    }
    return 0;
}