网站开发实现的功能,网站上哪个做相片书好,前端seo搜索引擎优化,建设网校目录 原题描述#xff1a;
题目描述
输入格式#xff1a;
输出格式#xff1a;
样例输入#xff1a;
样例输出#xff1a;
数据范围#xff1a;
提示#xff1a;
主要思路#xff1a;
code: 原题描述#xff1a;
题目描述
在某个遥远的国家里#xff0c;有…目录 原题描述
题目描述
输入格式
输出格式
样例输入
样例输出
数据范围
提示
主要思路
code: 原题描述
题目描述
在某个遥远的国家里有n个城市。编号为1,2,3,…,n。这个国家的政府修建了m条双向道路每条道路连接着两个城市。政府规定从城市S到城市T需要收取的过路费为所经过城市之间道路长度的最大值。如A到B长度为2B到C长度为3那么开车从A经过B到C需要上交的过路费为3。 佳佳是个做生意的人需要经常开车从任意一个城市到另外一个城市因此他需要频繁地上交过路费由于忙于做生意所以他无时间来寻找交过路费最低的行驶路线。然而当他交的过路费越多他的心情就变得越糟糕。作为秘书的你需要每次根据老板的起止城市提供给他从开始城市到达目的城市最少需要上交多少过路费。 输入格式
第一行是两个整数n 和m分别表示城市的个数以及道路的条数。 接下来m行每行包含三个整数 abw1≤ab≤n0≤w≤10^9表示a与b之间有一条长度为w的道路。 接着有一行为一个整数q表示佳佳发出的询问个数。 再接下来q行每一行包含两个整数ST1≤S,T≤nS≠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≤10001≤m≤100001≤q≤100 对于50%的数据满足1≤ n≤100001≤m≤100001≤q≤10000 对于100%的数据满足1≤ n≤100001≤m≤1000001≤q≤10000 提示
remove!!!
主要思路
这题是树上求最大值我们可以证明最小代价路径一定在最小生成树上所以要用Kruskal和并查集。
接着有树就会有LCA我们在树上求个最大值famax[i][j]是从i向上跳所到达的点。
famax的初始化和fa的初始化差不多。
那具体LCA怎么求不会请自行上网查找。
只要在LCA里加一个取max就可以了。
code:
#includebits/stdc.h
using namespace std;
int n,m;
vectorvectorpairint,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 wW.w;}
}a[400010];
int find(int x)
{if(fath[x] x){return x;}return fath[x] find(fath[x]);
}
void Kruskal()
{sort(a1,a1m);for(int i1;im;i){int xfind(a[i].x),yfind(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 i0;fa[x][i];i){fa[x][i1] fa[fa[x][i]][i];famax[x][i1] 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 ans0;if(depth[x]depth[y]){swap(x,y);}for(int i20;i0;--i){int ddepth[x]-depth[y];if((1i)d){ans max(famax[x][i],ans);x fa[x][i];}}if(x y){return ans;}for(int i__lg(depth[x]);i0;--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);cinnm;for(int i1;im;i){cina[i].xa[i].ya[i].w;}for(int i1;in;i){fath[i] i;}Kruskal();dfs(1,0);int q;cinq;while(q--){int s,t;cinst;coutLCA(s,t)\n;}return 0;
}
