題解 UVA11354 【Bond】

并查集+按秩合并

我們可以發現，跑最小生成樹會跑挂， 那麼任意兩點， 在生成樹上有唯一路徑， 而且這條路徑上的最大危險值一定最小。 但是每次詢問最大複雜度O(n)， 那麼複雜度高達O(n^2)。 我們知道， 并查集在用了路徑壓縮之後效率高達O(n)， 但是卻破壞了樹形結構， 是以不能用路徑壓縮。 然而僅僅靠按秩合并， 複雜度也可低至O(logn)。 是以我們隻需按秩合并， 然後詢問的時候向根回溯就行了， 複雜度mlogn。

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
#define R register int
using namespace std;
const int N=50010;
int f[N],rk[N],w[N],wi[N];
int n,m,t,u,v,cs;

struct edge{
    int u,v,w;
}e[N];

inline bool cmp(const edge& x,const edge& y) {return x.w<y.w;}

void init() {for(R i=0;i<=n;i++) f[i]=i,rk[i]=0,w[i]=0;}

inline int getf(int i) {return f[i]==i?i:getf(f[i]);}

inline void merge(int u,int v,int wi)
{
    u=getf(u),v=getf(v);
    if(u==v) return ;
    if(rk[u]<rk[v]) f[u]=v,w[u]=wi;
    else 
    {
        f[v]=u,w[v]=wi;
        if(rk[u]==rk[v]) rk[u]++;
    }
}

inline int solve(int u,int v)
{
    for(R i=0;i<=n;i++) wi[i]=0;
    R ans=1,ans1=0;
    while(1) { wi[u]=ans; if(f[u]==u) break; ans=max(ans,w[u]),u=f[u];}
    while(1)
        if(wi[v]) {ans1=max(ans1,wi[v]); break;}
        else if(f[v]==v) break;
        else ans1=max(ans1,w[v]),v=f[v];    
    return ans1;
}

int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        if(cs++) putchar('\n');
        init();
        for(R i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
        sort(e+1,e+m+1,cmp);
        for(R i=1;i<=m;i++) merge(e[i].u,e[i].v,e[i].w);
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&u,&v);
            printf("%d\n",solve(u,v));
        }    
    }
    return 0;
}