货车运输

题目描述

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入输出格式

输入格式：

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道

路。接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意： x 不等于 y，两座城市之间可能有多条道路。

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

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

输出格式：

输出文件名为 truck.out。

输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货

车不能到达目的地，输出-1。

输入输出样例

输入样例#1：

输出样例#1：

说明

对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q< 1,000；

对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q< 1,000；

对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q< 30,000，0 ≤ z ≤ 100,000。

题解：

求最大生成树，然后在最大生成树上跑LCA。

因为是最大生成树，所以这样得到的路径最小值必定是题目所要求的答案。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int n,m,l,ans[],lim;

 int father[];

 struct node{int from,to,dis;}map[];

 int find(int x){if(father[x]==x)return x;else return father[x]=find(father[x]);}

 bool cmp(const node a,const node b){return a.dis>b.dis;}

 struct question{int s,t,id;}que[];

 int head[],size=;

 struct Node{int next,to,dis;}edge[];

 void putin(int from,int to,int dis){size++;edge[size].dis=dis;edge[size].to=to;edge[size].next=head[from];head[from]=size;}

 int fa[][],mmin[][],vis[],dep[];

 void dfs(int r,int depth)

 {

     vis[r]=;

     dep[r]=depth;

     for(int i=head[r];i!=-;i=edge[i].next)

     {

         int y=edge[i].to;

         if(!vis[y])

         {

             fa[y][]=r;

             mmin[y][]=edge[i].dis;

             dfs(y,depth+);

         }

     }

 }

 void RMQ()

 {

     for(int i=;i<=lim;i++)

         for(int j=;j<=n;j++)

         {

             fa[j][i]=fa[fa[j][i-]][i-];

             mmin[j][i]=min(mmin[j][i-],mmin[fa[j][i-]][i-]);

         }

 }

 int LCA(int x,int y)

 {

     int i,j,ans=;

     if(dep[x]<dep[y])swap(x,y);

     for(i=lim;i>=;i--)

         if(dep[x]-(<<i)>=dep[y])

         {

             ans=min(ans,mmin[x][i]);

             x=fa[x][i];

         }

     if(x!=y)

     {

         for(i=lim;i>=;i--)

         {

             if(fa[x][i]!=fa[y][i])

             {

                 ans=min(ans,min(mmin[x][i],mmin[y][i]));

                 x=fa[x][i];

                 y=fa[y][i];

             }

         }

         ans=min(ans,min(mmin[x][],mmin[y][]));

         x=fa[x][];

         y=fa[y][];

     }

     return ans;

 }

 int main()

 {

     int i,j;

     memset(head,-,sizeof(head));

     memset(ans,-,sizeof(ans));

     memset(mmin,/,sizeof(mmin));

     scanf("%d%d",&n,&m);lim=log2(n);

     for(i=; i<=n; i++)father[i]=i;

     for(i=; i<=m; i++)scanf("%d%d%d",&map[i].from,&map[i].to,&map[i].dis);

     sort(map+,map+m+,cmp);

     for(i=; i<=m; i++)

     {

         int p=find(map[i].from),q=find(map[i].to);

         if(p!=q)

         {

             father[p]=q;

             putin(p,q,map[i].dis);

             putin(q,p,map[i].dis);

         }

     }

     scanf("%d",&l);

     for(i=;i<=n;i++)if(father[i]==i)dfs(i,);

     RMQ();

     for(i=; i<=l; i++)

     {

         int from,to;

         scanf("%d%d",&from,&to);

         if(find(from)==find(to))printf("%d\n",LCA(from,to));

         else printf("-1\n");

     }

     return ;

 }

货车