P1967 货车运输
题目描述
A 国有 nnn 座城市，编号从 11 1 到 n nn，城市之间有 mmm 条双向道路。每一条道路对车辆都有重量限制，简称限重。
现在有 qqq 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入格式
第一行有两个用一个空格隔开的整数 n,m 表示 A国有 n nn 座城市和 m条道路。接下来 m行每行三个整数 x,y,z，每两个整数之间用一个空格隔开，表示从 x号城市到 y号城市有一条限重为 z的道路。注意： x≠yx
eq yx�=y，两座城市之间可能有多条道路 。 接下来一行有一个整数 q，表示有 q 辆货车需要运货。 接下来 q 行，每行两个整数 x,y之间用一个空格隔开，表示一辆货车需要从 x城市运输货物到 y城市，保证 x≠yx
eq yx�=y
输出格式
共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。 如果货车不能到达目的地，输出 −1。
题解：求出最大生成树，再求lca，倍增维护路径上边权最小值。
代码：（感谢gjz大佬debug）；
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define maxn 10005
#define INF 0x3f3f3f3f
int fa[maxn],cnt,ans;
int w[maxn][14];
bool vis[maxn];
struct node{int u,v,w;}e[maxn*5];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
bool cmp(node a,node b){return a.w>b.w;}
int n,m,s;
int cnt1,head[maxn],depth[maxn],p[maxn][14];
struct Edge{
int nxt,to,val;
}edge[2*maxn];
void add(int x,int y,int z){
edge[++cnt1].nxt=head[x];
edge[cnt1].val=z;
head[x]=cnt1;
edge[cnt1].to=y;
}
void dfs(int node)
{
for(int i=1;i<=13;i++){
p[node][i]=p[p[node][i-1]][i-1];
w[node][i]=min(w[node][i-1],w[p[node][i-1]][i-1]);
}
vis[node]=true;
for(int i=head[node]; i; i=edge[i].nxt){
int to=edge[i].to;
if(vis[to]) continue;
depth[to]=depth[node]+1;
p[to][0]=node;
w[to][0]=edge[i].val;
dfs(to);
}
return;
}
int lca(int x, int y){
if(find(x)!=find(y))return -1;
int ans=INF;
if(depth[x]>depth[y])swap(x,y);
for(int i=13;i>=0;i--)
if(depth[p[y][i]]>=depth[x]){
ans=min(ans,w[y][i]);
y=p[y][i];
}
if(x==y)return ans;
for(int i=13; i>=0; i--)
if(p[x][i]!=p[y][i]){
ans=min(ans,min(w[x][i],w[y][i]));
x=p[x][i];
y=p[y][i];
}
ans=min(ans,min(w[x][0],w[y][0]));
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e+1,e+1+m,cmp);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
if(find(e[i].u)==find(e[i].v))continue;
fa[find(e[i].u)]=find(e[i].v);
add(e[i].u,e[i].v,e[i].w);
add(e[i].v,e[i].u,e[i].w);
if((++cnt)==n-1)break;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
depth[i]=1;
dfs(i);
}
}
int q;scanf("%d",&q);
int x,y;
while(q--){
scanf("%d%d",&x,&y);
printf("%d
",lca(x,y));
}
return 0;
}
P2245 星际导航
同理，变成求最小生成树。