图的最小生成树

A 国有 nnn 座城市，编号从 11 1 到 n nn，城市之间有 mmm 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 qqq 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

第一行有两个用一个空格隔开的整数 n,m n,mn,m，表示 AAA 国有 n nn 座城市和 mmm 条道路。

接下来 mmm 行每行三个整数 x,y,zx, y, zx,y,z，每两个整数之间用一个空格隔开，表示从 xx x 号城市到 y y y 号城市有一条限重为 zzz 的道路。
注意： x≠yx \neq yx?=y，两座城市之间可能有多条道路 。

接下来一行有一个整数 qqq，表示有 qqq 辆货车需要运货。

接下来 qqq 行，每行两个整数 x,yx,yx,y，之间用一个空格隔开，表示一辆货车需要从 xxx 城市运输货物到 yyy 城市，保证 x≠yx \neq yx?=y

共有 qqq 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 −1-1−1。

对于 30%30\%30% 的数据，1≤n<10001 \le n < 10001≤n<1000，1≤m<10,0001 \le m < 10,0001≤m<10,000，1≤q<10001\le q< 10001≤q<1000；

对于 60%60\%60% 的数据，1≤n<10001 \le n < 10001≤n<1000，1≤m<5×1041 \le m < 5\times 10^41≤m<5×104，1≤q<10001 \le q< 10001≤q<1000；

对于 100%100\%100% 的数据，1≤n<1041 \le n < 10^41≤n<104，1≤m<5×1041 \le m < 5\times 10^41≤m<5×104，1≤q<3×1041 \le q< 3\times 10^4 1≤q<3×104，0≤z≤1050 \le z \le 10^50≤z≤105。

思路：先构造最大生成树，在利用LCA算法求最小值（后半句话还没弄懂）

代码：

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int q;
int x,y;
int fa[10005][21],w[10005][21];
int f[10005];
int total;
struct node{
    int u,v;
    int w;
}edge[50005];
struct point{
    int to;
    int weight;
    int nxt;
}ep[100005];
int head[10005];
int cnt;
bool vis[10002];
int deep[10005];
bool com(node a,node b){
    return a.w >b.w ;
}
int find(int x){
    while(x!=f[x])x=f[x];
    return x;
}
void addedge(int x,int y,int z){
    cnt++;
    ep[cnt].to =y;
    ep[cnt].weight =z;
    ep[cnt].nxt =head[x];
    head[x]=cnt;
}
void kruskal(){
    sort(edge,edge+m,com);
    for(int i=0;i<m;i++){
        int eu=find(edge[i].u );
        int ev=find(edge[i].v );
        if(eu==ev)continue;
        f[ev]=eu;
        addedge(edge[i].u ,edge[i].v ,edge[i].w );
        addedge(edge[i].v ,edge[i].u ,edge[i].w );
    }
}
void dfs(int x){
    vis[x]=1;
    for(int i=head[x];i;i=ep[i].nxt){
       int t=ep[i].to ;
       if(vis[t])continue;
       deep[t]=deep[x]+1;
       fa[t][0]=x;
       w[t][0]=ep[i].weight ;
       dfs(t);    
    }
}
int lca(int x,int y){
    if(find(x)!=find(y)) return -1;
    int ans=0x7fffffff;
    if(deep[x]>deep[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(deep[fa[y][i]]>=deep[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(ans,min(w[x][0],w[y][0]));
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>edge[i].u >>edge[i].v >>edge[i].w ;
    }
    for(int i=1;i<=n;i++)   f[i]=i;
    kruskal();
    for(int i=1;i<=n;i++){
        if(!vis[i]){
               deep[i]=1;
            dfs(i);
                fa[i][0]=i;
                w[i][0]=0x7fffffff;
        }
    }
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            fa[j][i]=fa[fa[j][i-1]][i-1];
            w[j][i]=min(w[j][i-1],w[fa[j][i-1]][i-1]);
        }
    }
    cin>>q;
    
    for(int i=1;i<=q;i++){
        cin>>x>>y;
        cout<<lca(x,y)<<endl;
    }
}

三、出题 总结

1、如果有出发点和终点，那大部分应该选prim算法。

2、大部分会在n-k，k条边停止。

3、可能给点坐标会 自己建完全图，构造最大生成树。