P1967 货车运输

YTC

https://www.luogu.org/problemnew/show/P1967


题目描述

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 。

输入输出样例

输入样例#1：

4 3

1 2 4

2 3 3

3 1 1

3

1 3

1 4

1 3

输出样例#1：

3

-1

3

YTC

kruskal求最大生成树，倍增求出最大限重，再lca求解

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<queue>
   
4. #include<cstring>
   
5. #include<algorithm>
   
6. #include<cmath>
   
7. using namespace std;
   
8. struct node1{int x;int y;int z;}e1[100005];
   
9. struct node{int to;int next;int dis;}edge[100005];
   
10. int n,m,qq,num,t;
    
11. int d[10001],head[10001];
    
12. int cmp(node1 a,node1 b){return a.z>b.z;}
    
13. queue<int> q;
    
14. void add(int x,int y,int z)
    
15. {
    
16.     edge[++num].to=y;
    
17.     edge[num].dis=z;
    
18.     edge[num].next=head[x];
    
19.     head[x]=num;
    
20. }
    
21. int fa[10001],w[10001][21],f[10001][21];
    
22. int get(int x)
    
23. {
    
24.     if(fa[x]==x) return x;
    
25.     return fa[x]=get(fa[x]);
    
26. }
    
27. void unionn(int x,int y)
    
28. {
    
29.     x=get(x);y=get(y);
    
30.     fa[x]=y;
    
31. }
    
32. void bfs(int s)
    
33. {
    
34.     while(!q.empty()) q.pop();
    
35.     d[s]=1;
    
36.     q.push(s);
    
37.     while(!q.empty())
    
38.     {
    
39.     int x=q.front();
    
40.     q.pop();
    
41.     for(int i=head[x];i;i=edge[i].next)
    
42.     {
    
43.         int y=edge[i].to;
    
44.         if(d[y]) continue;
    
45.         d[y]=d[x]+1;
    
46.         f[y][0]=x;
    
47.         w[y][0]=edge[i].dis;
    
48.         q.push(y);
    
49.     }
    
50.     }
    
51. }
    
52. int lca(int x,int y)
    
53. {
    
54.     if(d[x]>d[y]) swap(x,y);
    
55.     int ans=0x7fffffff;
    
56.     for(int i=t;i>=0;i--)
    
57.     {
    
58.         if(d[f[y][i]]>=d[x])
    
59.         {
    
60.             ans=min(ans,w[y][i]);
    
61.             y=f[y][i];
    
62.         }
    
63.     }
    
64.     if(x==y) return ans;
    
65.     for(int i=t;i>=0;i--)
    
66.         if(f[x][i]!=f[y][i])
    
67.     {
    
68.         ans=min(ans,min(w[x][i],w[y][i]));
    
69.         x=f[x][i];
    
70.         y=f[y][i];
    
71.     }
    
72.     ans=min(ans,min(w[x][0],w[y][0]));
    
73.     return ans;
    
74. }
    
75. int main()
    
76. {
    
77.     cin>>n>>m;
    
78.     t=log(n)/log(2)+1;
    
79.     for(int i=1;i<=m;i++)
    
80.     {
    
81.         int x,y,z;
    
82.         cin>>x>>y>>z;
    
83.         e1[i].x=x;
    
84.         e1[i].y=y;
    
85.         e1[i].z=z;
    
86.     }
    
87.     for(int i=1;i<=n;i++) fa[i]=i;
    
88.     sort(e1+1,e1+1+m,cmp);
    
89.     for(int i=1;i<=m;i++)
    
90.         if(get(e1[i].x)!=get(e1[i].y))
    
91.     {
    
92.         add(e1[i].x,e1[i].y,e1[i].z);
    
93.         add(e1[i].y,e1[i].x,e1[i].z);
    
94.         unionn(e1[i].x,e1[i].y);
    
95.     }
    
96.     for(int i=1;i<=n;i++)
    
97.         if(!d[i]) bfs(i);
    
98.     for(int i=1;i<=t;i++)
    
99.         for(int j=1;j<=n;j++)
    
100.     {
     
101.         f[j][i]=f[f[j][i-1]][i-1];
     
102.         w[j][i]=min(w[j][i-1],w[f[j][i-1]][i-1]);
     
103.     }
     
104.     cin>>qq;
     
105.     for(int i=1;i<=qq;i++)
     
106.     {
     
107.         int x,y;
     
108.         cin>>x>>y;
     
109.         if(get(x)!=get(y)) cout<<-1<<endl;
     
110.         else cout<<lca(x,y)<<endl;
     
111.     }
     
112.     return 0;
     
113. }
     

复制代码