过路费的题解

目录

原题描述：

题目描述

输入格式：

输出格式：

样例输入：

样例输出：

数据范围：

提示：

主要思路：

code:

---

原题描述：

题目描述

在某个遥远的国家里，有n个城市。编号为1,2,3,…,n。这个国家的政府修建了m条双向道路，每条道路连接着两个城市。政府规定从城市S到城市T需要收取的过路费为所经过城市之间道路长度的最大值。如：A到B长度为2，B到C长度为3，那么开车从A经过B到C需要上交的过路费为3。
佳佳是个做生意的人，需要经常开车从任意一个城市到另外一个城市，因此他需要频繁地上交过路费，由于忙于做生意，所以他无时间来寻找交过路费最低的行驶路线。然而，当他交的过路费越多他的心情就变得越糟糕。作为秘书的你，需要每次根据老板的起止城市，提供给他从开始城市到达目的城市，最少需要上交多少过路费。

输入格式：

第一行是两个整数n 和m，分别表示城市的个数以及道路的条数。
接下来m行，每行包含三个整数 a，b，w（1≤a，b≤n，0≤w≤10^9），表示a与b之间有一条长度为w的道路。
接着有一行为一个整数q，表示佳佳发出的询问个数。
再接下来q行，每一行包含两个整数S，T（1≤S,T≤n，S≠T）, 表示开始城市S和目的城市T。

输出格式：

输出文件共q行，每行一个整数，分别表示每个询问需要上交的最少过路费用。输入数据保证所有的城市都是连通的。

样例输入：

4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1

样例输出：

20
20

数据范围：

对于30%的数据，满足1≤ n≤1000，1≤m≤10000，1≤q≤100；
对于50%的数据，满足1≤ n≤10000，1≤m≤10000，1≤q≤10000；
对于100%的数据，满足1≤ n≤10000，1≤m≤100000，1≤q≤10000；

提示：

remove!!!

主要思路：

这题是树上求最大值，我们可以证明，最小代价路径一定在最小生成树上，所以要用Kruskal和并查集。

接着，有树，就会有LCA，我们在树上求个最大值，famax[i][j]是从i向上跳所到达的点。

famax的初始化和fa的初始化差不多。

那具体LCA怎么求，不会请自行上网查找。

只要在LCA里加一个取max就可以了。

code:
 

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<pair<int,int>>> v(400010);
int depth[400010];
int fa[400010][40];
int fath[400010];
int famax[400010][40];
struct edgenode{int x,y,w;bool operator < (const edgenode& W)const{return w<W.w;}
}a[400010];
int find(int x)
{if(fath[x] == x){return x;}return fath[x] = find(fath[x]);
}
void Kruskal()
{sort(a+1,a+1+m);for(int i=1;i<=m;i++){int x=find(a[i].x),y=find(a[i].y);if(x!=y){fath[x] = y;v[x].push_back({y,a[i].w});v[y].push_back({x,a[i].w});}}
}
void dfs(int x,int fat)
{fa[x][0] = fat;for(int i=0;fa[x][i];++i){fa[x][i+1] = fa[fa[x][i]][i];famax[x][i+1] = max(famax[x][i],famax[fa[x][i]][i]);}for(auto it:v[x]){if(it.first!=fat){depth[it.first] = depth[x]+1;famax[it.first][0] = it.second;dfs(it.first,x);}}
}
int LCA(int x,int y)
{int ans=0;if(depth[x]<depth[y]){swap(x,y);}for(int i=20;i>=0;--i){int d=depth[x]-depth[y];if((1<<i)&d){ans = max(famax[x][i],ans);x = fa[x][i];}}if(x == y){return ans;}for(int i=__lg(depth[x]);i>=0;--i){	if(fa[x][i]!=fa[y][i]){ans = max({ans,famax[x][i],famax[y][i]});x = fa[x][i];y = fa[y][i];}}ans = max({ans,famax[x][0],famax[y][0]});return ans;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1;i<=m;i++){cin>>a[i].x>>a[i].y>>a[i].w;}for(int i=1;i<=n;i++){fath[i] = i;}Kruskal();dfs(1,0);int q;cin>>q;while(q--){int s,t;cin>>s>>t;cout<<LCA(s,t)<<'\n';}return 0;
}