TZOJ 4848 货车运输(最大生成树+倍增lca)

描述

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

输入

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

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

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

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

输出

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

样例输入

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

样例输出

3
-1
3

提示

对于 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

查询u，v的最小值的时候，先找到u，v的公共祖先p，再求min（up的最小值，vp的最小值）

代码

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 const int maxm=;

 int deep[maxn],fa[maxn][],dis[maxn][],lg[maxn],vis[maxn],f[maxn],n,m;

 vector< pair<int,int> >G[maxn];

 struct edge

 {

     int u,v,w;

     bool operator<(const edge &D)const{

         return w>D.w;

     }

 }edges[maxm];

 void dfs(int u)

 {

     vis[u]=;

     for(auto X:G[u])

     {

         int v=X.first;

         int w=X.second;

         if(vis[v])continue;

         fa[v][]=u;

         dis[v][]=w;

         deep[v]=deep[u]+;

         dfs(v);

     }

 }

 void RNQ()

 {

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

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

             fa[i][j]=fa[fa[i][j-]][j-],

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

 }

 int lca(int x,int y)

 {

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

     while(deep[x]>deep[y])x=fa[x][lg[deep[x]-deep[y]]-];

     if(x==y)return x;

     for(int k=lg[deep[x]];k>=;k--)

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

             x=fa[x][k],y=fa[y][k];

     return fa[x][];

 }

 int find(int x)

 {

     return f[x]==x?x:f[x]=find(f[x]);

 }

 int query(int x,int y)

 {

     int ans=0x3f3f3f3f,t=deep[x]-deep[y];

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

         if(t&(<<i))

             ans=min(ans,dis[x][i]),

             x=fa[x][i];

     return ans;

 }

 void max_kruskal()

 {

     int cnt=;

     sort(edges,edges+m);

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

     {

         int u=edges[i].u;

         int v=edges[i].v;

         int w=edges[i].w;

         int fu=find(u);

         int fv=find(v);

         if(fu!=fv)

         {

             G[u].push_back({v,w});

             G[v].push_back({u,w});

             f[fu]=fv;

             if(++cnt==n-)break;

         }

     }

 }

 int main()

 {

     memset(dis,0x3f3f3f3f,sizeof dis);

     memset(vis,false,sizeof vis);

     int u,v,w,q;

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)lg[i]=lg[i-]+(<<lg[i-]==i),f[i]=i;

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

     {

         scanf("%d%d%d",&u,&v,&w);

         edges[i]={u,v,w};

     }

     max_kruskal();

     for(int i=;i<=n;i++)if(!vis[i])dfs(i);

     RNQ();

     scanf("%d",&q);

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

     {

         scanf("%d%d",&u,&v);

         if(find(u)!=find(v))printf("-1\n");

         else

         {

             int father=lca(u,v);

             printf("%d\n",min(query(u,father),query(v,father)));

         }

     }

     return ;

 }

巴特西

TZOJ 4848 货车运输(最大生成树+倍增lca)

最新文章

热门文章