题意:
有n个点,(n<=200)
给出每个点的坐标,任意两个点之间都有一条边。
从第一个点到第二个点可以有很多条路,每条路包含不同的边。
每条路中的最长边记为 maxi ,
求所有的 maxi 中最小的那个。
即所有的路径中最长边中最小的那个。
分析:
可以用最短路来做,但是感觉用最小生成树做思路更清晰。
200个点,最大不会超过40000个边,可以用kruskal
每次选取不成环的最小边,直到树中加入了某条边后,
使得起点和终点在同一条边中,
那么最后选择的这条边必然是在树中最大的一条边,
而且在其余的边中是最小的。
不会找到比这条边小的最大距离,因为比它小的最小距离都在树里了。
而之前树中起点终点不连通,即比该边小的所有边无法到达终点。
代码:
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 200+1;
struct Node
{
double x, y;
}a[MAXN];
struct Edge
{
int a,b;
double d;
}E[MAXN*MAXN];
bool cmp(Edge a, Edge b)
{
return a.d < b.d;
}
double getDis(int i, int j)
{
return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+
(a[i].y-a[j].y)*(a[i].y-a[j].y));
}
int R[MAXN];
int Find(int x)
{
return x==R[x] ? R[x] : R[x] = Find(R[x]);
}
bool Union(int a, int b)
{
int Ra = Find(a);
int Rb = Find(b);
if (Ra != Rb)
{
R[Ra] = Rb;
return true;
}
return false;
}
int main()
{
int n, cnt = 1;
while (cin >> n && n)
{
for (int i = 0; i < n; i++)
{
cin >> a[i].x >> a[i].y;
R[i] = i;
}
int cntE = 0;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
E[cntE].a = i, E[cntE].b = j, E[cntE++].d = getDis(i,j);
sort(E,E+cntE,cmp);
double res;
for (int i = 0; i < cntE; i++)
{
if (Union(E[i].a, E[i].b))
{
if (Find(0) == Find(1))
{
res = E[i].d;
break;
}
}
}
cout << "Scenario #" << cnt++ << endl;
cout << "Frog Distance = ";
printf("%.3lf\n",res);
cout << endl;
}
return 0;
}
Comments | NOTHING