首页 > 代码库 > UvaOJ10369 - Arctic Network
UvaOJ10369 - Arctic Network
1 /* 2 The first line of each test case contains 1 <= S <= 100, the number of satellite channels! 3 注意:S表示一共有多少个卫星,那么就是有 最多有S-1个通道! 然后将最小生成树中的后边的 S-1通道去掉就行了! 4 思路:最小生成树中的第 k 个最小边! 5 */ 6 //克鲁斯克尔算法..... 7 #include<iostream> 8 #include<cstdio> 9 #include<cstring>10 #include<algorithm>11 #include<cmath>12 using namespace std;13 14 double x[800], y[800];15 16 struct node{17 int u, v; 18 double d;19 };20 21 bool cmp(node a, node b){22 return a.d < b.d;23 }24 25 int f[505];26 27 node nd[150000];28 double ret[505];29 30 int getFather(int x){31 return x==f[x] ? x : f[x]=getFather(f[x]);32 }33 34 bool Union(int a, int b){35 int fa=getFather(a), fb=getFather(b);36 if(fa!=fb){37 f[fa]=fb;38 return true;39 }40 return false;41 }42 43 int main(){44 int n, m;45 int t;46 scanf("%d", &t);47 while(t--){48 scanf("%d%d", &m, &n);49 for(int i=1; i<=n; ++i){50 scanf("%lf%lf", &x[i], &y[i]);51 f[i]=i;52 }53 int cnt=0;54 for(int i=1; i<n; ++i)55 for(int j=i+1; j<=n; ++j){56 nd[cnt].u=i;57 nd[cnt].v=j;58 nd[cnt++].d=sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));59 }60 sort(nd, nd+cnt, cmp);61 int cc=0;62 for(int i=0; i<cnt; ++i)63 if(Union(nd[i].u, nd[i].v))64 ret[cc++]=nd[i].d;65 for(int i=0; i<cc; ++i)66 cout<<ret[i]<<"fdsf"<<endl;67 printf("%.2lf\n", ret[n-m-1]);68 }69 return 0;70 }
1 //prim算法....... 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 using namespace std; 8 const double INF = 0x3f3f3f3f*1.0; 9 double x[800], y[800];10 11 int n, m;12 double map[505][505];13 int vis[505];14 15 double ret[505];16 17 void prim(){18 memset(vis, 0, sizeof(vis));19 vis[1]=1;20 for(int i=2; i<=n; ++i)21 ret[i]=INF;22 int root=1, p;23 for(int i=1; i<n; ++i){24 double minLen=INF; 25 for(int j=2; j<=n; ++j){26 if(!vis[j] && ret[j]>map[root][j])27 ret[j]=map[root][j];28 if(!vis[j] && minLen>ret[j]){29 minLen=ret[j];30 p=j; 31 }32 }33 root=p;34 vis[root]=1;35 }36 }37 38 int main(){39 40 int t;41 scanf("%d", &t);42 while(t--){43 scanf("%d%d", &m, &n);44 for(int i=1; i<=n; ++i)45 scanf("%lf%lf", &x[i], &y[i]);46 for(int i=1; i<n; ++i)47 for(int j=i+1; j<=n; ++j)48 map[i][j]=map[j][i]=sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));49 50 prim();51 sort(ret, ret+n+1);52 53 printf("%.2lf\n", ret[n-m+1]);54 }55 return 0;56 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。