思路

考虑答案的运输路径。发现：能走限重大的就走。

所以要尽量把限重小的边删掉，只要图仍然联通就行。问题就转变成用最小值最大的边联通这个图。这就是最大生成树，可以用\(kruskal\)求出。

之后每次运输要使最小限重最大。但是发现有些边必须要走，而剩下的路径越短越好。\(LCA\)即可。由于图不一定联通，要分别对每个联通块预处理。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int n,m,s,x,y,z;const int MAXN=10005,MAXM=50005;struct edge{    int to,next,dis;}tree[MAXN*2];int depth[MAXN],lg2[MAXN],head[MAXN],fa[MAXN][25],pre[MAXN][25],eg,f[MAXN],temp,ask;struct ne{    int from,to,dis;}ng[MAXM];inline bool comp(ne e1,ne e2){    return e1.dis>e2.dis;}int add(int from,int to,int dis){    tree[++eg].to=to;    tree[eg].dis=dis;    tree[eg].next=head[from];    head[from]=eg;}int fread(){    char c=getchar();    int num=0;    while(c>='0'&&c<='9')        num=num*10+c-'0',c=getchar();    return num;}int get_depth(int node,int father){    depth[node]=depth[father]+1;    fa[node][0]=father;        for(int i=1;i<=lg2[depth[node]]-1;i++)    {        fa[node][i]=fa[fa[node][i-1]][i-1];        pre[node][i]=min(pre[node][i],pre[node][i-1]);        pre[node][i]=min(pre[node][i],pre[fa[node][i-1]][i-1]);    }    for(int i=head[node];i;i=tree[i].next)        if(tree[i].to!=father)            pre[tree[i].to][0]=tree[i].dis,get_depth(tree[i].to,node);}inline void merge(int n1,int n2){    f[n1]=n2;}inline int find(int num){    if(num==f[num]) return num;    return f[num]=find(f[num]);}int kruskal(){    int cnt=0;    sort(ng+1,ng+1+m,comp);    for(int i=1;i<=n;i++)        f[i]=i;    for(int i=1;i<=m;i++)    {        if(find(ng[i].from)==find(ng[i].to))            continue;        f[find(ng[i].from)]=find(ng[i].to);        add(ng[i].from,ng[i].to,ng[i].dis),add(ng[i].to,ng[i].from,ng[i].dis);    }}inline int LCA(int x,int y){    if(find(x)!=find(y)) return -1;    int ans=114514810;    if(depth[x]
         
          depth[y]) { ans=min(ans,pre[x][lg2[depth[x]-depth[y]]-1]); x=fa[x][lg2[depth[x]-depth[y]]-1]; } if(x==y) return ans; for(int i=lg2[depth[x]]-1;i>=0;i--) if(fa[x][i]!=fa[y][i]) ans=min(ans,pre[x][i]),ans=min(ans,pre[y][i]),x=fa[x][i],y=fa[y][i]; ans=min(ans,pre[x][0]),ans=min(ans,pre[y][0]); return ans;}int main(){ scanf("%d %d",&n,&m); memset(pre,0x3f,sizeof(pre)); for(int i=1;i<=m;i++) scanf("%d %d %d",&x,&y,&z),ng[i].from=x,ng[i].to=y,ng[i].dis=z; kruskal(); for(int i=1;i<=MAXN;i++) lg2[i]=lg2[i-1]+(1<
          
           >ask; for(int i=1;i<=ask;i++) { scanf("%d %d",&x,&y); temp=LCA(x,y); printf("%d\n",temp); } return 0;}