学步园

题目链接：http://poj.org/problem?id=2349

————————————————————————————————————————————————

题目大意： 有p个城市，s个卫星，卫星是装在一个城市上的（这点很重要），有卫星的城市之间可以任意通讯。

                    所有城市都装有无线电，没有卫星的城市是用无线电来通讯的，城市间的距离越大，无线电通讯的成本就越高。

                    问，若所有城市都能直接，或者间接连在一起（即该图是连通的），需要用无线电通讯的城市间最大的距离的最小值是多少。

————————————————————————————————————————————————

题目思路：    <克鲁斯卡尔>

即求做一最小生成树，去掉其中的 s-1条 最大的边就可以了。

关于这样做的正确性，可以这么理解。生成最小生成树的过程，也是不断的将点合并的过程， 加一个边，就合并在一个连通分量里。

加了p -s 条边以后，图被分成了几个连通分量，刚好一个连通分量里有一个卫星与另外的连通分量进行通讯。

显然这 p-s条边 每一步都是最优的。

————————————————————————————————————————————————

源代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;

struct et
{
   double val;
   int v;
   int u;

   int operator >(const et &e) const
   {
       if(val>e.val) return true;
       else return false;
   }

}edge[125000];

struct vt
{
    double x;
    double y;
    int fat;
}ver[510];

int s = 0,p = 0;
int k = 0,ans[510],m = 0;

double d(vt a,vt b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

bool cmp(et a,et b)
{
    return !(a>b);
}

int findfat(int i)
{
    int f = 0;

    if(ver[i].fat == i)
      return i;
    else
    {
        f = findfat(ver[i].fat);
        ver[i].fat = f;
        return f;
    }
}

void kruskal()
{
    int i = 0;
    int uf = 0,vf = 0;

    m = 0;
    for(i = 0;i<k;i++)
    {
        if((uf = findfat(edge[i].u)) != (vf = findfat(edge[i].v)))
        {
            ver[uf].fat = vf;                      //不为ver[v].fat，因为vf可能更靠近根。此处WA，一定是更改u的father的father，只是更改u的father是错误的！
            ans[m++] = i;
            if(m>=p-1)
              break;
        }
    }
}

int main()
{
    int n = 0;
    int i = 0,x = 0,y = 0,j = 0;

    scanf("%d",&n);
    while((n--)>0)
    {
        k = 0;
        scanf("%d%d",&s,&p);
        for(i = 1;i<=p;i++)
        {
            scanf("%d%d",&x,&y);
            ver[i].x = x;
            ver[i].y = y;
            ver[i].fat = i;
            for(j = 1;j<i;j++)
            {
                edge[k].v = i;
                edge[k].u = j;
                edge[k++].val = d(ver[i],ver[j]);
            }
        }
        sort(edge,edge+k,cmp);
        kruskal();

        m = m-s;
        if(s == 0)
         m = m-1;
        if(p == 1)
          printf("0.00\n");
        else
          printf("%.2f\n",edge[ans[m]].val);
    }

    return 0;
}