poj2253-Frogger(最小生成树)

发布于 2019-08-12  519 次阅读


问题传送门:

题意:

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

Simple And Clear