Description
\(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\) 。
Output
共有 \(q\) 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出 \(-1\) 。
4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3
Sample Output
3 -1 3
HINT
对于 \(30%\) 的数据，\(0 < n < 1,000,0 < m < 10,000,0 < q< 1,0000<n<1,000,0<m<10,000,0<q<1,000\)
对于 \(60%\) 的数据， \(0 < n < 1,000,0 < m < 50,000,0 < q< 1,0000<n<1,000,0<m<50,000,0<q<1,000\)
对于 \(100%\) 的数据， \(0 < n < 10,000,0 < m < 50,000,0 < q< 30,000,0 ≤ z ≤ 100,0000<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,000\)
题解
也是一道比较经典最小瓶颈树题目。
$Kruskal + lca倍增 $ 贪心想法，边权由小向大加，用并查集维护连通性。然后一想发现这就是 \(Kruskal\) 感觉这题跟今年 \(NOI d1t1\) 有些像啊，那道说是什么 \(Kruskal重构树\) ……
顺便提一个结论： 其实最小生成树就是最小瓶颈树，这是可以证明滴~（想想 \(Kruskal\) 的贪心过程就可以明白）
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10005;
struct node{
int v,len;
node *next;
}pool[N*2],*h[N];
int cnt;
void addedge(int u,int v,int len){
node *p=&pool[++cnt],*q=&pool[++cnt];
p->v=v;p->next=h[u];h[u]=p;p->len=len;
q->v=u;q->next=h[v];h[v]=q;q->len=len;
}
int n,m;
int f[N][15],fmin[N][15],dep[N];
void dfs(int u){
int v;
for(node *p=h[u];p;p=p->next)
if(!dep[v=p->v]){
dep[v]=dep[u]+1;
f[v][0]=u; fmin[v][0]=p->len;
for(int j=1;j<15;j++){
f[v][j]=f[f[v][j-1]][j-1];
fmin[v][j]=min(fmin[v][j-1],fmin[f[v][j-1]][j-1]);
}
dfs(v);
}
}
int query(int x,int y){
int ret=100005;
if(dep[x]<dep[y]) swap(x,y);
for(int i=14;i>=0;i--)
if(dep[f[x][i]]>=dep[y]) ret=min(ret,fmin[x][i]),x=f[x][i];
if(x==y) return ret;
for(int i=14;i>=0;i--)
if(f[x][i]!=f[y][i]){
ret=min(ret,min(fmin[x][i],fmin[y][i]));
x=f[x][i]; y=f[y][i];
}
ret=min(ret,min(fmin[x][0],fmin[y][0]));
return ret;
}
struct edge{
int x,y,z;
bool operator < (const edge &b) const { return z>b.z; }
}ed[N*5];
int fa[N];
int getfa(int x) { return fa[x]==x ? x : fa[x]=getfa(fa[x]) ; }
void merge(int x,int y){
x=getfa(x); y=getfa(y);
fa[x]=y;
}
int main()
{
int x,y,q;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++) scanf("%d%d%d",&ed[i].x,&ed[i].y,&ed[i].z);
sort(ed,ed+m);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=0;i<m;i++){
if(getfa(ed[i].x)==getfa(ed[i].y)) continue;
addedge(ed[i].x,ed[i].y,ed[i].z);
merge(ed[i].x,ed[i].y);
}
for(int j=0;j<15;j++) fmin[0][j]=100005;
for(int i=1;i<=n;i++){
if(dep[i]) continue;
for(int j=0;j<15;j++) fmin[i][j]=100005;
dep[i]=1;
dfs(i);
}
scanf("%d",&q);
while(q--){
scanf("%d%d",&x,&y);
if(getfa(x)!=getfa(y)) printf("-1\n");
else printf("%d\n",query(x,y));
}
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/9733447.html
相关资源：数据结构—成绩单生成器
