【UVA534】Frogger 最小瓶颈路

题目大意：给定一张 N 个点的完全图，求 1，2 号节点之间的一条最小瓶颈路。

题解：可知，最小瓶颈路一定存在于最小生成树（最小瓶颈树）中。因此，直接跑克鲁斯卡尔算法，当 1，2 号节点在同一个联通块时，即可停止算法，并输出答案即可。

代码如下

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn=210;

const int maxe=4e4+10;

struct node{double x,y;}p[maxn];

struct edge{

	int from,to;double w;

	edge(int from=0,int to=0,double w=0):from(from),to(to),w(w){}

}e[maxe];

int tot,n,kase,f[maxn];

bool cmp(const edge& x,const edge& y){return x.w<y.w;}

inline double get_dis(int a,int b){

	return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));

}

void read_and_parse(){

	tot=0;

	for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);

	for(int i=1;i<=n;i++)

		for(int j=i+1;j<=n;j++)

			e[++tot]=edge(i,j,get_dis(i,j));

}

int find(int x){

	return x==f[x]?x:f[x]=find(f[x]);

}

double kruskal(int from,int to){

	sort(e+1,e+tot+1,cmp);

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

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

		int x=find(e[i].from),y=find(e[i].to);

		if(x==y)continue;

		f[x]=y;

		if(find(from)==find(to))return e[i].w;

	}

	return 0;

}

void solve(){

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

	printf("Frog Distance = %.3lf\n\n",kruskal(1,2));

}

int main(){

	while(scanf("%d",&n)&&n){

		read_and_parse();

		solve();

	}

	return 0;

}

巴特西

【UVA534】Frogger 最小瓶颈路

最新文章

热门文章