题目描述

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。

输出格式

输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货
车不能到达目的地，输出-1。

关于最小权值最大

这个问题叫做最大瓶颈路径，最大瓶颈路径一定存在于最大生成树中。
反证法：如果最大瓶颈路径不存在与最大生成树中。
这些不在最大生成树中的边会和最大生成树形成环。
我们删掉环上最小的边，保留这一条边，会得到一棵新的更大的生成树。
这与原来那棵树是最大生成树矛盾了。
注意，最短路不一定在最小生成树上（如一个环的情况）

题解

它只问最大，所以可以直接转化成Kruskal最大生成树，然后一边倍增lca一边预处理一下，就可以像lca那样log查询了。

注意

容易产生一个误区，倍增过程中处理最小权边，会不会产生遗漏乜？
答案是不会。
事实上是查询lca的时候是绝对会遗漏的，但是即使遗漏，只要是这条路径（从儿子找爸爸路径唯一，不考虑兄弟分叉），上面的会dp（min）选择下面的路权。
所以做到不遗漏的是建立st表的时候的不遗漏，观察代码（getst），会发现倍增是全图处理 2k 2 k fa后才会处理 2k+1 2 k + 1 fa，所以一定是包含的，所以不遗漏。

代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
int n,m;
const int MAXN=11000;
const int MAXM=51000;
struct edgess{int u,v,w;}edge[MAXM];int tot;
struct arress{int to,co,next;}arr[MAXM<<1];int head[MAXN],cnt;
void add (int u,int v,int w){edge[++tot].u=u;edge[tot].v=v;edge[tot].w=w;}
bool cmp(const edgess a,const edgess b){return a.w>b.w;}
void adds(int u,int v,int w){arr[++cnt].to=v;arr[cnt].co=w;arr[cnt].next=head[u];head[u]=cnt;}
int pre[MAXN];
int find(int x){return x==pre[x]?x:pre[x]=find(pre[x]);}
void kruscal()
{
sort(edge+1,edge+m+1,cmp);
for(int i=1;i<=n;i++)pre[i]=i;
for(int i=1,j=n;i<=m&&j!=1;i++)
{
int a=find(edge[i].u);
int b=find(edge[i].v);
if(a!=b)
{
pre[b]=a;
j--;
adds(edge[i].u,edge[i].v,edge[i].w);
adds(edge[i].v,edge[i].u,edge[i].w);
}
}
}
int fa[MAXN][18],dep[MAXN],mn[MAXN][18];
bool vis[MAXN];
void dfs(int s,int dad,int cost)
{
vis[s]=1;
fa[s][0]=dad;
mn[s][0]=cost;
dep[s]=dep[dad]+1;
for(int e=head[s];~e;e=arr[e].next)
{
int t=arr[e].to;
if(t==dad)continue;
dfs(t,s,arr[e].co);
}
}
void getst()
{
for(int i=1;i<=n;i++)
if(vis[i]==0){vis[i]=1;dfs(i,0,0);}
for(int k=1;k<=16;k++)
for(int i=1;i<=n;i++)
{
fa[i][k]=fa[fa[i][k-1]][k-1];
mn[i][k]=min(mn[fa[i][k-1]][k-1],mn[i][k-1]);
}
}
int getlca(int x,int y)
{
int ans=0x7f7f7f7f;
if(dep[x]>dep[y])
swap(x,y);
for(int k=16;k>=0;k--)
{
if(fa[y][k])
if(dep[fa[y][k]]>=dep[x])
{
ans=min(ans,mn[y][k]);
y=fa[y][k];
if(dep[x]==dep[y])break;
}
}
if(x==y)return ans;
for(int k=16;k>=0;k--)
{
if(fa[y][k]!=fa[x][k])
{
ans=min(ans,mn[y][k]);
ans=min(ans,mn[x][k]);
y=fa[y][k];x=fa[x][k];
}
}
return min(ans,min(mn[y][0],mn[x][0]));
}
int main()
{
scanf("%d%d",&n,&m);
mem(head,-1);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
kruscal();
getst();
int q;
scanf("%d",&q);
for(int i=1,x,y;i<=q;i++)
{
scanf("%d%d",&x,&y);
if(find(x)!=find(y))printf("-1n");
else
printf("%dn",getlca(x,y));
}
//system("pause");
return 0;
}

最后

以上就是糊涂睫毛为你收集整理的洛谷 P1967 货车运输【NOIP2013D1T3】（最大生成树+倍增LCA）题目描述关于最小权值最大题解注意代码的全部内容，希望文章能够帮你解决洛谷 P1967 货车运输【NOIP2013D1T3】（最大生成树+倍增LCA）题目描述关于最小权值最大题解注意代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。