BZOJ 3732 Network

题目大意

多次询问一个无向图A到B的所有路径中的一条，使得最大值最小。

和货车运输一样……Kruskal+LCA.

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,k,inx,iny,fa[15010][21],fat[15010],depth[15010],cnt,dis[15010][21];
int to[100001],nex[100001],val[100001],head[15010],tot;
struct edge
{
	int u,v,w;
}e[30010];
bool cmp(edge tx,edge ty) {return tx.w<ty.w;}
void addedge(int tx,int ty,int tz) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;}
int unifind(int tx) {return fat[tx]==tx?tx:fat[tx]=unifind(fat[tx]);}
void kruskal()
{
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=n;++i) fat[i]=i;
	for(int i=1;i<=m;++i)
	{
		int tx=unifind(e[i].u),ty=unifind(e[i].v);
		if(tx!=ty)
		{
			++cnt;
			fat[tx]=ty;
			addedge(e[i].u,e[i].v,e[i].w);
			addedge(e[i].v,e[i].u,e[i].w);
			if(cnt==n-1) return;
		}
	}
}
void dfs(int pos)
{
	for(int i=head[pos];i;i=nex[i])
		if(!depth[to[i]])
		{
			depth[to[i]]=depth[pos]+1;
			fa[to[i]][0]=pos;
			dis[to[i]][0]=val[i];
			dfs(to[i]);
		}
}
void init()
{
	kruskal();
	depth[1]=1;
	dfs(1);
	for(int i=1;i<=20;++i)
		for(int j=1;j<=n;++j)
		{
			fa[j][i]=fa[fa[j][i-1]][i-1];
			dis[j][i]=max(dis[j][i-1],dis[fa[j][i-1]][i-1]);
		}
}
int query(int tx,int ty)
{
	int ret=0;
	if(depth[tx]<depth[ty]) swap(tx,ty);
	for(int i=20;~i;i--)
		if(depth[fa[tx][i]]>=depth[ty]) ret=max(ret,dis[tx][i]),tx=fa[tx][i];
	for(int i=20;~i;--i)
		if(fa[tx][i]!=fa[ty][i]) ret=max(ret,max(dis[tx][i],dis[ty][i])),tx=fa[tx][i],ty=fa[ty][i];
	return tx==ty?ret:max(ret,max(dis[tx][0],dis[ty][0]));
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	init();
	while(k--)
	{
		scanf("%d%d",&inx,&iny);
		printf("%d\n",query(inx,iny));
	}
	return 0;
}