图论系列：

前言：

相关题单：戳我

一.最小瓶颈路

唉，前面4个题单里其实有不少题是最小瓶颈路的做法啊。讲解摘自 wiki 。

1.定义

无向图 \(G\) 中 \(x\) 到 \(y\) 的最小瓶颈路是这样的一类简单路径，满足这条路径上的最大的边权在所有 \(x\) 到 \(y\) 的简单路径中是最小的。（对于下面这张图， \(2 \to 3\) 的最小瓶颈路就是 \(2 \to 1 \to 5 \to 3\) ，此时经过路径最大值为 \(4\)）。

相当于你需要一定的等级才能走一条边（这就是边权），问你需要从 \(x\) 走到 \(y\) 所需要的最小等级。将所有小于等于此等级的边添加如图中，图中每一条 \(x \to y\) 的路径都是最小瓶颈路。

2.性质

根据最小生成树定义，\(x\) 到 \(y\) 的最小瓶颈路上的最大边权等于最小生成树上 \(x\) 到 \(y\) 路径上的最大边权。虽然最小生成树不唯一，但是每种最小生成树 \(x\) 到 \(y\) 路径的最大边权相同且为最小值。也就是说，每种最小生成树上的 \(x\) 到 \(y\) 的路径均为最小瓶颈路。

但是，并不是所有最小瓶颈路都存在一棵最小生成树满足其为树上 \(x\) 到 \(y\) 的简单路径。

3.应用

由于最小瓶颈路不唯一（如上图中最小瓶颈路还可以是 \(2 \to1 \to 5\to 4 \to 3\) ），一般情况下会询问最小瓶颈路上的最大边权。也就是说，我们需要求最小生成树链上的 max，倍增、树剖都可以解决。

给一道板子题，先将最小生成树建出来后判断链上边权最大值即可（注意可能最后图可能不连通，可能会生成一个最小生成树森林）。

代码：

//采用的是树剖+倍增求解
const int M=1e3+5,N=1e5+5;
int n,m,q;
int fax[M],vis[M],deep[M],fa[M][19],dis[M][19];

struct node{
	int u,v,w;
	inline bool operator <(const node o) const
	{
		return w<o.w;
	}
};node e[N];

int cnt=0;
struct Edge{
	int to,next,val;
};Edge p[N<<1];
int head[M];
inline void add(int a,int b,int c)
{
	++cnt;
	p[cnt].next=head[a];
	head[a]=cnt;
	p[cnt].to=b;
	p[cnt].val=c;
}
inline int find(int x)
{
	if(x!=fax[x]) fax[x]=find(fax[x]);
	return fax[x];
}

inline void dfs(int u,int f)
{
	fa[u][0]=f,deep[u]=deep[f]+1,vis[u]=1;
	for(int i=head[u];i!=0;i=p[i].next)
	{
		int v=p[i].to;
		if(v==f) continue;
		dis[v][0]=p[i].val;
		dfs(v,u);
	}
}

inline int lca(int x,int y)
{
	if(deep[x]<deep[y]) swap(x,y);
	int c=deep[x]-deep[y],res=0;
	for(int i=0;i<=18;++i)
	{
		if(c&(1<<i)) res=max(res,dis[x][i]),x=fa[x][i];
	}
	for(int i=18;i>=0;--i)
	{
		if(fa[x][i]!=fa[y][i])
		{
			res=max(res,max(dis[x][i],dis[y][i]));
			x=fa[x][i],y=fa[y][i];
		}
	}
	if(x==y) return res;
	res=max(res,max(dis[x][0],dis[y][0]));
	return res;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=n;++i) fax[i]=i;
	for(int i=1;i<=m;++i) cin>>e[i].u>>e[i].v>>e[i].w;
	sort(e+1,e+m+1);
	for(int i=1,x,y;i<=m;++i)
	{
		x=find(e[i].u),y=find(e[i].v);
		if(x==y) continue;
		fax[x]=y;
		add(e[i].u,e[i].v,e[i].w),add(e[i].v,e[i].u,e[i].w);
	}
	for(int i=1;i<=n;++i) if(!vis[i]) dfs(i,0);
	for(int j=1;j<=18;++j)
	{
		for(int i=1;i<=n;++i)
		{
			fa[i][j]=fa[fa[i][j-1]][j-1];
			dis[i][j]=max(dis[i][j-1],dis[fa[i][j-1]][j-1]);
		}
	}//倍增处理
	int x,y;
	while(q--)
	{
		cin>>x>>y;
		if(find(x)!=find(y)) cout<<"-1\n";
		else cout<<lca(x,y)<<"\n";
	}
	return 0;
}

二.Kruskal 重构树

1.定义：