货车运输

thelast · 2020-01-23 17:09:16 · 个人记录

挺难的。。。。。。。。。。。。。。。

应该先是最大生成树，当然，由于不一定各个点相连，所以必须以每个点为根尝试。

然后是lca倍增求点，与模板的区别在于边权，关键是lca退出之前还要再比较一次（类比模板），不然0分

#include<bits/stdc++.h>
using namespace std;
int n,m,q1,head[10001],num,fa[10001],deep[10001],fath[10001][21],w[10001][21];
struct edge1{int fr,to,w;} f1[50010];
struct edge2{int to,next,w;} f[50010];
void add(int a,int b,int c){
    f[++num].to=b;
    f[num].w=c;
    f[num].next=head[a];
    head[a]=num;return;
};
bool cmp(edge1 a,edge1 b)  {return a.w>b.w;}
int fin(int x){
    if(fa[x]!=x)fa[x]=fin(fa[x]);
    return fa[x];
}
void kurkal(){
    for(int i=1;i<=n;i++)fa[i]=i;
    sort(f1+1,f1+1+m,cmp);
    int k=0;
    for(int i=1;i<=m;i++){
        int x=f1[i].fr,y=f1[i].to;
        int r1=fin(x),r2=fin(y);
        if(r1!=r2){
            k++;
            fa[r2]=r1;
            add(x,y,f1[i].w),add(y,x,f1[i].w);
        }
        if(k==n-1)return;
    }
}
void dfs(int r){
    for(int i=head[r];i;i=f[i].next){
        int y=f[i].to;
        if(deep[y]==0){
            deep[y]=deep[r]+1;
            fath[y][0]=r;
            w[y][0]=f[i].w;
            dfs(y);
        }
    }
    return;
}
int lca(int a,int b){
    if(fin(a)!=fin(b))return -1;
    int ans=21474837;
    if(deep[a]<deep[b])swap(a,b);
    for(int i=20;i>=0;i--)
        if(deep[fath[a][i]]>=deep[b]){
            ans=min(ans,w[a][i]);
            a=fath[a][i];
        }
    if(a==b)return ans;
    for(int i=20;i>=0;i--)
        if(fath[a][i]!=fath[b][i]){
            ans=min(ans,min(w[a][i],w[b][i]));
            a=fath[a][i],b=fath[b][i];
        }
    ans=min(ans,min(w[a][0],w[b][0]));
    return ans;
}
int main(){
    cin>>n>>m;
    for(int a,b,c,i=1;i<=m;i++)
        scanf("%d%d%d",&f1[i].fr,&f1[i].to,&f1[i].w);
    kurkal();
    for(int i=1;i<=n;i++)
        if(deep[i]==0){
            deep[i]=1;
            dfs(i);
        }
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++){
            fath[j][i]=fath[fath[j][i-1]][i-1];
            w[j][i]=min(w[j][i-1],w[fath[j][i-1]][i-1]);
        }
    cin>>q1;
    for(int a,b,i=1;i<=q1;i++){
        scanf("%d%d",&a,&b);
        printf("%d\n",lca(a,b));
    }
    return 0;
}