Prim!
/*
prim
题意:给定一些点,一些卫星,一个卫星能连接两个点,点和点之间通信有一定的距离限制。
问能使得所有的点联通的最小距离。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int maxn = 505;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-8;
struct Node{
double x,y;
}a[ maxn ];
int vis[ maxn ];
double dis[ maxn ];
double mat[ maxn ][ maxn ];
double dist( Node a,Node b ){
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
void init( int n ){
for( int i=1;i<=n;i++ ){
for( int j=1;j<=n;j++ ){
mat[i][j] = dist( a[i],a[j] );
}
}
return ;
}
void prim( int n ){
for( int i=1;i<=n;i++ ){
vis[ i ] = 0;
dis[ i ] = mat[1][i];
}
vis[ 1 ] = 1;
for( int i=1;i<=n;i++ ){
int M = inf;
int id = -1;
for( int j=1;j<=n;j++ ){
if( vis[ j ]==0&&M>dis[j] ){
M = dis[ j ];
id = j;
}
}
if( id==-1 ) return ;
vis[ id ] = 1;
for( int j=1;j<=n;j++ ){
if( vis[j]==0&&dis[j]>mat[ id ][ j ] ){
dis[ j ] = mat[ id ][ j ];
}
}
}
return ;
}
int main(){
int T;
scanf("%d",&T);
while( T-- ){
int s,n;
scanf("%d%d",&s,&n);
for( int i=1;i<=n;i++ )
scanf("%lf%lf",&a[i].x,&a[i].y);
init( n );
prim( n );
sort( dis+1,dis+1+n );
//for( int i=1;i<=n;i++ )
// printf("%lf ",dis[ i ]);
//puts("");
printf("%.2lf\n",dis[ n-s+1 ]);
}
return 0;
}
分享到:
相关推荐
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ2485-Highways【Prim】 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
北大POJ1789-Truck History【Prim】 解题报告+AC代码
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1705139
poj1789 Truck History prim
NULL 博文链接:https://128kj.iteye.com/blog/1704752
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) .....
Algorithm-Java Algorithms + Data Structures = Programs....最短路径(dijkstra,bellman-ford,floyd,heap+dijkstra)(,,poj1062,poj2253,poj1125,poj2240) 最小生成树(prim,kruskal)(p
2.最小生成树(先写个prim,kruscal要用并查集,不好写) 3.大数(高精度)加减乘除 4.二分查找. (代码可在五行以内) 5.叉乘、判线段相交、然后写个凸包. 6.BFS、DFS,同时熟练hash表(要熟,要灵活,代码要简) ...
2.6 随机素数测试和大数分解 (POJ 1811) . . . . . . . . . . . . . . . . . . . . . . . 29 2.7 欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.7.1 分解质因素求...