题目描述
A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。
现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。
输入格式
第一行有两个用一个空格隔开的整数 n,m 表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行三个整数 x, y, z 每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。
注意:两座城市之间可能有多条道路 。
接下来一行有一个整数 q,表示有 q 辆货车需要运货。
接下来 q 行,每行两个整数 x,y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,保证 x!=y
输出格式
共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。
如果货车不能到达目的地,输出 -1。
人话题意:给任意两个点,求这两个点的简单路径上的边权最小值
首先贪心一下,建一个最大生成树,然后由于(一定)数据给的是森林,所以、应该从每个点都搜索一遍
之后用倍增的方法更新路上最小权值即可(我也不知到为啥我的只有用氧气优化才能过QAQ
#include <cstdio>
#include <iostream>
#include <algorithm>
#define Fo(i) for(int i=1;i<=q;i++)
#define For(i) for(int i=1;i<=n;i++)
using namespace std;
const int M=200005;
const int N=10005;
const int INF=2147483640;
int n,m,tot,head[M],q,cnt,fa[N],nex[M],to[M],v[M];
int f[N][30],w[N][30];
bool vis[N];
struct NODE{
int x,y,z;
bool operator <(const NODE &a){
return this->z >a.z;
}
}bian[M];
struct Node{
int dep,son,fa;
}dian[N];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9){
print(x/10);
}
putchar(x%10+'0');
}
inline void add(int x,int y,int z){
++tot;
nex[tot]=head[x];
to[tot]=y;
v[tot]=z;
head[x]=tot;
}
int find(int x){
if(fa[x]==x) return fa[x];
return find(fa[x]);
}
inline void kruskal(){
int p=0;
for(int i=1;i<=m;i++){
int fa1=find(bian[i].x);
int fa2=find(bian[i].y);
if(fa[fa1]!=fa[fa2]){
fa[fa1]=fa[fa2];
add(bian[i].x,bian[i].y,bian[i].z);
add(bian[i].y,bian[i].x,bian[i].z);
p++;
}
if(p==n-1) return ;
}
}
void dfs(int x){
vis[x]=1;
for(int i=head[x];i;i=nex[i]){
if(!vis[to[i]]){
w[to[i]][0]=v[i];
f[to[i]][0]=x;
dian[to[i]].dep=dian[x].dep+1;
dfs(to[i]);
}
}
return ;
}
int lca(int x,int y){
if(find(x)!=find(y)) return -1;
int ans=INF;
if(dian[x].dep>dian[y].dep) swap(x,y);
for(int i=20;i>=0;i--){
if(dian[x].dep<=dian[f[y][i]].dep){
ans=min(ans,w[y][i]);
y=f[y][i];
}
}
if(x==y) return ans;
for(int i=20;i>=0;i--){
if(f[x][i]!=f[y][i]){
ans=min(ans,(min(w[x][i],w[y][i])));
x=f[x][i];
y=f[y][i];
}
}
ans=min(ans,min(w[x][0],w[y][0]));
return ans;
}
int main(){
n=read();m=read();
For(i) fa[i]=i;
for(int i=1;i<=m;i++){
bian[i].x=read();
bian[i].y=read();
bian[i].z=read();
}
sort(bian+1,bian+m+1);
kruskal();
for(int i=1;i<=n;i++){
if(!vis[i]){
dian[i].dep=1;
dfs(i);
f[i][0]=i;
w[i][0]=INF;
}
}
for(int i=1; i<=20; i++)
for(int j=1; j<=n; j++){
f[j][i]=f[f[j][i-1]][i-1];
w[j][i]=min(w[j][i-1], w[f[j][i-1]][i-1]);
}
q=read();
Fo(i){
int x,y;
x=read();y=read();
print(lca(x,y));
printf("\n");
}
return 0;
}