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;
}