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算法.......
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double INF = 0x3f3f3f3f*1.0;
double x[800], y[800];

int n, m;
double map[505][505];
int vis[505];

double ret[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;
    }
}

int main(){
   
   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]);
       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]);
   }
   return 0;
}

目录
相关文章
|
机器学习/深度学习 数据挖掘 TensorFlow
How to Deploy a Neural Network on TH1520
How to Deploy a Neural Network on TH1520
297 0
How to Deploy a Neural Network on TH1520
Data Structures and Algorithms (English) - 7-11 Saving James Bond - Hard Version(30 分)
Data Structures and Algorithms (English) - 7-11 Saving James Bond - Hard Version(30 分)
152 0