倍增LCA经典题……

这题的做法就是求最大生成树，然后用倍增LCA法求瓶颈路……

注意一下，两点不连通时输出-1（其实这个用并查集判断不就行了……）！！！

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=10001,maxm=50001,maxlogn=15;
int n,m;

// edgeStruct
struct Edge{
    int u,v,d;
    friend bool operator < (const Edge& a,const Edge& b){
        return a.d>b.d;
    }
};
Edge EdgePool[maxm];

// Graph
vector<Edge> edges;
vector<int> G[maxn];
inline void Add_Edge(int x,int y,int c){
    edges.push_back((Edge){x,y,c});
    edges.push_back((Edge){y,x,c});
    int m=edges.size();
    G[x].push_back(m-2);
    G[y].push_back(m-1);
}

// DJ Set
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_dj_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
}

// MST
inline void mst(){
    register int i,k=0;
    sort(EdgePool,EdgePool+m);
    init_dj_set();
    for(i=0;i<m;i++){
        Edge& e=EdgePool[i];
        if(!is_same(e.u,e.v)){
            Add_Edge(e.u,e.v,e.d);
            union_set(e.u,e.v);
            k++;
            if(k==(n-1))
                break;
        }
    }
}

// DFS & LCA
int dep[maxn],par[maxn][maxlogn],mincost[maxn][maxlogn];
void dfs(int x,int depth,int fa){
    int i;
    dep[x]=depth;
    par[x][0]=fa;
    for(i=0;i<G[x].size();i++){
        Edge& e=edges[G[x][i]];
        if(e.v!=fa){
            mincost[e.v][0]=e.d;
            dfs(e.v,depth+1,x);
        }
    }
}
inline void init_LCA(){
    register int i,j,anc;
    for(j=1;(1<<j)<=n;j++)
        for(i=1;i<=n;i++)
            if(par[i][j-1]!=-1){
                anc=par[i][j-1];
                par[i][j]=par[anc][j-1];
                mincost[i][j]=min(mincost[i][j-1],mincost[anc][j-1]);
            }
}
int query(int x,int y){
    register int j,log,ans=0x4fffffff;
    if(dep[x]<dep[y])
        swap(x,y);
    for(log=1;(1<<log)<=dep[x];log++);
    log--;
    for(j=log;j>=0;j--)
        if((dep[x]-(1<<j))>=dep[y]){
            ans=min(ans,mincost[x][j]);
            x=par[x][j];
        }
    if(x==y)
        return ans;
    for(j=log;j>=0;j--)
        if(par[x][j]!=-1 && par[x][j]!=par[y][j]){
            ans=min(ans,mincost[x][j]);
            ans=min(ans,mincost[y][j]);
            x=par[x][j];
            y=par[y][j];
        }
    ans=min(ans,min(mincost[x][0],mincost[y][0]));
    return ans;
}
int main(){
    register int i;
    int a,b,c,q;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);
        EdgePool[i].u=a;
        EdgePool[i].v=b;
        EdgePool[i].d=c;
    }
    memset(par,-1,sizeof(par));
    mst();
    dfs(1,1,0);
    init_LCA();
    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&a,&b);
        if(is_same(a,b)){
            printf("%d\n",query(a,b));
        }else{
            puts("-1");
        }
    }
    return 0;
}

• 相关文章
• 全局相关文章