UvaOJ10369 - Arctic Network

/*

    The first line of each test case contains 1 <= S <= 100, the number of satellite channels!

    注意：S表示一共有多少個衛星，那麼就是有 最多有S-1個通道！ 然後将最小生成樹中的後邊的 S-1通道去掉就行了！ 

    思路：最小生成樹中的第 k 個最小邊！ 

*/

//克魯斯克爾算法.....

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

double x[800], y[800];

struct node{

   int u, v; 

   double d;

};

bool cmp(node a, node b){

    return a.d < b.d;

}

int f[505];

node nd[150000];

double ret[505];

int getFather(int x){

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

bool Union(int a, int b){

   int fa=getFather(a), fb=getFather(b);

   if(fa!=fb){

       f[fa]=fb;

       return true;

   }

   return false;

int main(){

   int n, m;

   int t;

   scanf("%d", &t);

   while(t--){

          scanf("%d%d", &m, &n);

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

          scanf("%lf%lf", &x[i], &y[i]);

          f[i]=i;

       }

       int cnt=0;

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

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

              nd[cnt].u=i;

              nd[cnt].v=j;

              nd[cnt++].d=sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));

          }

       sort(nd, nd+cnt, cmp);

       int cc=0;

       for(int i=0; i<cnt; ++i)

          if(Union(nd[i].u, nd[i].v))

             ret[cc++]=nd[i].d;

        for(int i=0; i<cc; ++i)

           cout<<ret[i]<<"fdsf"<<endl;

       printf("%.2lf\n", ret[n-m-1]);

   return 0;

}   

//prim算法.......

const double INF = 0x3f3f3f3f*1.0;

int n, m;

double map[505][505];

int vis[505];

void prim(){

    memset(vis, 0, sizeof(vis));

    vis[1]=1;

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

       ret[i]=INF;

    int root=1, p;

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

        double minLen=INF; 

        for(int j=2; j<=n; ++j){

           if(!vis[j] && ret[j]>map[root][j])

              ret[j]=map[root][j];

           if(!vis[j] && minLen>ret[j]){

              minLen=ret[j];

              p=j; 

           }

        }

        root=p;

        vis[root]=1;

    }

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

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

             map[i][j]=map[j][i]=sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));

       prim();

       sort(ret, ret+n+1);

       printf("%.2lf\n", ret[n-m+1]);

本文轉自 小眼兒 部落格園部落格，原文連結：http://www.cnblogs.com/hujunzheng/p/3899428.html，如需轉載請自行聯系原作者