題解 P1967 貨車運輸

題目描述

A 國有 n 座城市，編號從 1 到 n，城市之間有 m 條雙向道路。每一條道路對車輛都有重量限制，簡稱限重。現在有 q 輛貨車在運輸貨物，司機們想知道每輛車在不超過車輛限重的情況下，最多能運多重的貨物。

輸入

第一行有兩個用一個空格隔開的整數 n，m，表示 A 國有 n 座城市和 m 條道路。
接下來 m 行每行 3 個整數 x、y、z，每兩個整數之間用一個空格隔開，表示從 x 號城市到 y 號城市有一條限重為 z 的道路。註意：x 不等於 y，兩座城市之間可能有多條道路。
接下來一行有一個整數 q，表示有 q 輛貨車需要運貨。
接下來 q 行，每行兩個整數 x、y，之間用一個空格隔開，表示一輛貨車需要從 x 城市運輸貨物到 y 城市，註意：x 不等於 y。

輸出

輸出共有 q 行，每行一個整數，表示對於每一輛貨車，它的最大載重是多少。如果貨車不能到達目的地，輸出-1。

樣例輸入

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

樣例輸出

3
-1
3

提示

對於 30%的數據，0 < n < 1,000，0 < m < 10,000，0 < q < 1,000；
對於 60%的數據，0 < n < 1,000，0 < m < 50,000，0 < q < 1,000；
對於 100%的數據，0 < n < 10,000，0 < m < 50,000，0 < q < 30,000，0 ≤ z ≤ 100,000。

Solution

#include<bits/stdc++.h>
using namespace std;
struct zwc
{
    int x,y,z;
}a[100005];
int tot,n,m,Next[100005],head[100005],to[100005],f[100005],q,val[100005],fa[50005][23],dep[100005],w[50005][23];
bool vis[100005];
bool cmp(zwc x,zwc y)
{
    return x.z>y.z;
}
int findfa(int x)
{
    if (f[x]!=x) f[x]=findfa(f[x]);
    return f[x];
}
void add(int x,int y,int z)
{
    tot++;
    Next[tot]=head[x];
    to[tot]=y;
    val[tot]=z;
    head[x]=tot;
}
void dfs(int x)
{
    vis[x]=true;
    for (int i=head[x];i;i=Next[i])
    {
        int u=to[i];
        if (vis[u]) continue;
        dep[u]=dep[x]+1;
        fa[u][0]=x;
        w[u][0]=val[i];
        dfs(u);
    }
}
int lca(int x,int y)
{
    if (findfa(x)!=findfa(y)) return -1;
    int ans=1000000000;
    if (dep[x]>dep[y]) swap(x,y);
    for (int i=20;i>=0;i--)
    {
        if (dep[fa[y][i]]>=dep[x])
        {
            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])
        {
            ans=min(ans,min(w[x][i],w[y][i]));
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    ans=min(min(w[x][0],w[y][0]),ans);
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    }
    //kruskal
    sort(a+1,a+1+m,cmp);
    for (int i=1;i<=n;i++)
    f[i]=i;
    for (int i=1;i<=m;i++)
    {
        int p1=findfa(a[i].x);
        int p2=findfa(a[i].y);
        if (p1!=p2)
        {
            f[p1]=p2;
            add(a[i].x,a[i].y,a[i].z);
            add(a[i].y,a[i].x,a[i].z);
        }
    }
    //倍增+LCA 
    for (int i=1;i<=n;i++)
    {
        if (!vis[i])
        {
            dep[i]=1;
            dfs(i);
            fa[i][0]=i;
            w[i][0]=1000000000;
        }
    }
    for (int j=1;j<=20;j++)
    for (int i=1;i<=n;i++)
    {
        fa[i][j]=fa[fa[i][j-1]][j-1];
        w[i][j]=min(w[i][j-1],w[fa[i][j-1]][j-1]);
    }
    scanf("%d",&q);
    for (int i=1;i<=q;i++)
    {
        int x,y=0;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}