luogu题解 UVA534 【Frogger--最小瓶颈边

题目链接：

https://www.luogu.org/problemnew/show/UVA534
Update 6.18

多点对最短瓶颈路算法：https://www.cnblogs.com/Rye-Catcher/p/9194967.html
思路：

题意就是叫你求\(1,2\)点之间的最小瓶颈路，何谓最小瓶颈路呢？

对于无向图\(u,v\)两个顶点，若两个顶点有多条路径，设第\(i\)条路径经过边权最大的边权为\(w[i]\),那么\(u,v\)两点的最小瓶颈路就是\(min(w[i])\)

我们用Kruskal,将边权从小到大排序后构建MST,若加入两点\(u,v\)且\(fa[u]=1\) \(fa[v]=2\),则此时的边权\(edge(u,v)\)就是最小瓶颈路

为了上述处理过程我们用带权路径压缩并查集,\(rk[1]\) \(rk[2]\)设为很大的数(暴力的数)，以保证生成树中两点的祖先都是\(1\)或\(2\)

同时注意UVA很多题目的特点：毒瘤输出
代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cmath>

#include <cctype>

#include <cstring>

#define ri register int

#define ll long long

using namespace std;

const int maxn=205;

struct Edge{

	int u,v;

	double dis;

	bool operator<(const Edge & b)const{

		return dis<b.dis;

	}

}edge[1926081];

int n;

int fa[maxn],rk[maxn];

int px[maxn],py[maxn];

int get(int x){

	if(fa[x]!=x)fa[x]=get(fa[x]);

	return fa[x];

}

inline void merge(int x,int y){

	if(rk[x]>rk[y]){

		fa[y]=x;

		rk[x]+=rk[y];

	}

	else

	{

		fa[x]=y;

		rk[y]+=rk[x];

	}

	return ;

}

int main(){

	int u,v,e,t=0;

	while(scanf("%d",&n)!=EOF){

		if(!n)break;t++;

		int cnt=0,tot=0;

		for(ri i=1;i<=n;i++){

			fa[i]=i,rk[i]=0;

			scanf("%d %d",&px[i],&py[i]);

			for(ri j=1;j<i;j++){

				double d=sqrt((double)(px[i]-px[j])*(px[i]-px[j])+(double)(py[i]-py[j])*(py[i]-py[j]));

				edge[++tot].u=i,edge[tot].v=j;

				edge[tot].dis=d;

			}

		}

		rk[1]=rk[2]=1926817;

		sort(edge+1,edge+1+tot);

	    for(ri i=1;i<=tot;i++){

	    	u=edge[i].u,v=edge[i].v;

	    	u=get(u),v=get(v);

	    	if(u!=v){

	    		cnt++;

	    		if((u==1&&v==2)||(u==2&&v==1)){

	    			printf("Scenario #%d\n",t);

                    printf("Frog Distance = %.3lf\n\n",edge[i].dis);

	    			//printf("%.3lf\n",edge[i].dis);

	    			break;

				}

				else{

					merge(u,v);

				}

			}

			if(cnt==n-1)break;

		}

		memset(edge,0,sizeof(edge));

	}

	return 0;

}

巴特西

luogu题解 UVA534 【Frogger--最小瓶颈边

最新文章

热门文章