[TIOJ 1163] 6.施工中的道路

作法：

原題簡單來說就是給一張有權重的無向圖，每次詢問所有連接兩個點的路徑中，「路徑上最大的邊」的最小值。如果考慮最小生成樹的 Kruskal 算法，把邊按照邊權從小到大加進去，如果有兩個端點已經連通的就不理他，那麼可以知道 x 和 y 之間的答案就是讓 x 和 y 連通的時候加進來的那條邊(由算法的過程易證)，所以每次等於是在新的圖(會是原圖的最小生成森林)上詢問「x 到 y 的路徑上經過的邊的最大值」，而這可以用和LCA類似的倍增法得到。

另外，去年(103年)的全國賽第5題考的「求次小生成樹的權值和」也會用到「詢問x 到 y 的路徑上經過的邊的最大值」這件事，不過我當時還不會LCA，所以只寫了個 O(NM) 的作法( M 是原圖的邊數 )，只拿到70分QAQ 另外一種用 Union By Rank 的作法可以參考這裡。

對了，UVa10600也是次小生成樹，可以拿來練習，不過這題的範圍O(NM)就會過了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=30000+10 ;
struct P
{
    int from,to,dis;
    bool operator < (const P &rhs) const
    {
        return dis<rhs.dis ;
    }
};
struct Q{int to,dis;};
 
int fa[maxn] ;
int getfa(int x)
{
    return fa[x]==x ? x : fa[x]=getfa(fa[x]) ;
}
 
vector<Q> v[maxn] ;
int n,dep[maxn] ;
int anc[17][maxn],ancdis[17][maxn] ;
 
void dfs(int x,int f,int d)
{
    dep[x]=d ;
    for(auto i : v[x]) if(i.to!=f)
    {
        anc[0][i.to]=x ;
        ancdis[0][i.to]=i.dis ;
        dfs(i.to,x,d+1) ;
    }
}
 
void build_LCA()
{
    memset(anc[0],-1,sizeof(anc[0])) ;
    for(int i=1;i<=n;i++) if(anc[0][i]==-1)
    {
        anc[0][i]=i ;
        ancdis[0][i]=0 ;
        dfs(i,i,0) ;
    }
    for(int i=1;(1<<i)<=n;i++) for(int j=1;j<=n;j++)
        anc[i][j]=anc[i-1][anc[i-1][j]] ,
        ancdis[i][j]=max(ancdis[i-1][j],ancdis[i-1][anc[i-1][j]]) ;
}
 
void query_fa(int x,int num,int &ans,int &dis)
{
    if(!num) { ans=x ; dis=0 ; return ; }
    dis=0 ;
    for(int i=16;i>=0 && num;i--) if(num&(1<<i))
        dis=max(dis,ancdis[i][x]) , x=anc[i][x] ,
        num^=(1<<i) ;
    ans=x ;
}
 
int LCA(int x,int y)
{
    if(x==y) return 0 ;
    if(dep[x]>dep[y])
    {
        int f,d ;
        query_fa(x,dep[x]-dep[y],f,d) ;
        return max(d,LCA(f,y)) ;
    }
    if(dep[x]<dep[y])
    {
        int f,d ;
        query_fa(y,dep[y]-dep[x],f,d) ;
        return max(d,LCA(x,f)) ;
    }
    int ret=0 ;
    for(int i=15;i>=0;i--) if(anc[i][x]!=anc[i][y])
        ret=max(ret,max(ancdis[i][x],ancdis[i][y])) ,
        x=anc[i][x] , y=anc[i][y] ;
    return max(ret,max(ancdis[0][x],ancdis[0][y])) ;
}
 
vector<P> edge ;
main()
{
    int m ; scanf("%d%d",&n,&m) ;
    while(m--)
    {
        int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
        edge.push_back((P){x,y,dis}) ;
    }
    sort(edge.begin(),edge.end()) ;
    for(int i=1;i<=n;i++) fa[i]=i ;
    for(auto i : edge)
    {
        int x=getfa(i.from) , y=getfa(i.to) ;
        if(x==y) continue ;
        fa[x]=y ;
        v[i.from].push_back((Q){i.to,i.dis}) ;
        v[i.to].push_back((Q){i.from,i.dis}) ;
    }
 
    build_LCA() ;
    int Q ; scanf("%d",&Q) ;
    while(Q--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        if(getfa(x)!=getfa(y)) printf("-1\n") ;
        else printf("%d\n",LCA(x,y)) ;
    }
}