Kruskal+LCA【p2245】星际导航

Description

sideman做好了回到Gliese 星球的硬件准备，但是sideman的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有$N$ 个顶点和$M$ 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。

sideman 现在想把危险程度降到最小，具体地来说，就是对于若干个询问(A, B)，sideman 想知道从顶点$A$ 航行到顶点$B$ 所经过的最危险的边的危险程度值最小可能是多少。作为sideman 的同学，你们要帮助sideman 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

Input

第一行包含两个正整数$N$ 和$M$，表示点数和边数。

之后 $M$ 行，每行三个整数$A$，$B $和$L$，表示顶点$A$ 和$B$ 之间有一条边长为$L$ 的边。顶点从$1$ 开始标号。

下面一行包含一个正整数 $Q$，表示询问的数目。

之后 $Q$ 行，每行两个整数$A$ 和$B$，表示询问$A$ 和$B$ 之间最危险的边危险程度的可能最小值。

Output

对于每个询问，在单独的一行内输出结果。如果两个顶点之间不可达，输出$impossible$。

woc这不是$Noip\ 2013$货车运输.

切掉!

显然,我们可以发现.想要让一些顶点联通,并且让最危险的边的危险程度值最小。

优先想到了$Kruskal$.

首先$Kruckal$建树。

如何求两点间的距离?带权$LCA$即可.

如果两点不在一颗树,要输出$impossible$!!

刚开始输出错了

注意如果写两个结构体的话,对其中一个$Sort$(建树)的话,不要结构体中重载$<$

代码

#include<cstdio>

#include<algorithm>

#include<cctype>

#define R register

#define N 100008

using namespace std;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int n,m,head[N],tot,q;

int fa[N],cnt,depth[N],f[N][21],gw[N][21];

struct cod{int u,v,w;}edge[300010],tree[300010];

inline bool ccp(const cod&a,const cod&b)

{

	return a.w<b.w;

}

int find(int x){return fa[x]==x ? x : fa[x]=find(fa[x]);}

inline void add(int x,int y,int z)

{

	edge[++tot].u=head[x];

	edge[tot].v=y;

	edge[tot].w=z;

	head[x]=tot;

}

inline void kruskal()

{

	for(R int i=1;i<=n;i++)fa[i]=i;

	sort(tree+1,tree+m+1,ccp);

	for(R int i=1;i<=m;i++)

	{

		int u=tree[i].u,v=tree[i].v,w=tree[i].w;

		int fu=find(u),fv=find(v);

		if(fu==fv)continue;

		add(u,v,w);add(v,u,w);

		fa[fu]=fv;cnt++;

		if(cnt==n-1)break;

	}

	return ;

}

void dfs(int u,int fat,int dis)

{

	depth[u]=depth[fat]+1;

	gw[u][0]=dis;f[u][0]=fat;

	for(R int i=1;(1<<i)<=depth[u];i++)

	{

		f[u][i]=f[f[u][i-1]][i-1];

		gw[u][i]=max(gw[u][i-1],gw[f[u][i-1]][i-1]);

	}

	for(R int i=head[u];i;i=edge[i].u)

	{

		if(edge[i].v==fat)continue;

		dfs(edge[i].v,u,edge[i].w);

	}

}

inline int lca(int x,int y)

{

	int res=-214748364;

	if(depth[x]>depth[y])swap(x,y);

	for(R int i=20;i>=0;i--)

		if(depth[x]+(1<<i)<=depth[y])

			res=max(res,gw[y][i]),y=f[y][i];

	if(x==y)return res;

	for(R int i=20;i>=0;i--)

	{

		if(f[x][i]==f[y][i])continue;

		res=max(res,gw[x][i]);

		res=max(res,gw[y][i]);

		x=f[x][i],y=f[y][i];

	}

	return max(max(res,gw[x][0]),gw[y][0]);

}

int main()

{

	in(n),in(m);

	for(R int i=1;i<=m;i++)

		in(tree[i].u),in(tree[i].v),in(tree[i].w);

	kruskal();

	dfs(1,0,0);

	in(q);

	for(R int i=1,x,y;i<=q;i++)

	{

		in(x),in(y);

		R int fx=find(x),fy=find(y);

		if(fx!=fy)puts("impossible");

		else printf("%d\n",lca(x,y));

	}

}

巴特西

Kruskal+LCA【p2245】星际导航

Description

Input

Output

最新文章

热门文章

巴特西

Kruskal+LCA【p2245】 星际导航

Description

Input

Output

最新文章

热门文章

Kruskal+LCA【p2245】星际导航