poj 2349 Arctic Network （prim算法）

Description

Input

Output

Sample Input

1
2 4
0 100
0 300
0 600
150 750

Sample Output

212.13

最小生成树prim算法

#include"stdio.h"
#include"math.h"
#include"string.h"
#include"queue"
#include"algorithm"
using namespace std;
#define N 505
const double inf=1e12;
double g[N][N],dis[N];
bool mark[N];
int n,m;
struct node
{
    double x,y;
}e[N];
double fun(int i,int j)
{
    double x,y;
    x=e[i].x-e[j].x;
    y=e[i].y-e[j].y;
    return sqrt(x*x+y*y);
}
void prim(int s)
{
    int i,j,u;
	double min;
    memset(mark,0,sizeof(mark));
    mark[s]=1;
    for(i=0;i<m;i++)
    {
        dis[i]=g[s][i];
    }
	dis[s]=0;
    for(j=1;j<m;j++)
    {
        u=s;
        min=inf;
        for(i=0;i<m;i++)
        {
            if(!mark[i]&&dis[i]<min)
            {
                min=dis[i];
                u=i;
            }
        }
        mark[u]=1;
        for(i=0;i<m;i++)
        {
            if(!mark[i]&&dis[i]>g[u][i])
                dis[i]=g[u][i];
        }
    }
    sort(dis,dis+m);        //从小到大排序
    printf("%.2f\n",dis[m-n]);
}
int main()
{
    int T,i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++)
        {
            scanf("%lf%lf",&e[i].x,&e[i].y);
        }
        for(i=0;i<m;i++)
        {
            for(j=0;j<i;j++)
            {
                g[i][j]=g[j][i]=fun(i,j);
            }
            g[i][i]=inf;       //注意初始化
        }
        prim(0);
    }
    return 0;
}

poj 2349 Arctic Network （prim算法）,布布扣,bubuko.com

poj 2349 Arctic Network （prim算法）

原文：http://blog.csdn.net/u011721440/article/details/38708423