今天碰到一個(gè)最小生成樹(shù)（數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)算法）
鞏固了一下 沒(méi)有什么大的收獲。
不過(guò)發(fā)現(xiàn)原來(lái)在程序后面加個(gè)system("pause")也能AC;
代碼如下：
#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAX 101
#define INFINITE 1000000000
struct node
{
double a;
double b;
}dot[MAX];
double value[MAX][MAX];
bool visit[MAX];
double dis[MAX];
int n;
double distance(int i,int j)
{
double temp=0;
temp=sqrt((dot[i].a-dot[j].a)*(dot[i].a-dot[j].a)+(dot[i].b-dot[j].b)*(dot[i].b-dot[j].b));
return temp;
}
double prim()
{
double sum=0;
int i,j;
int k;
memset(visit,false,sizeof(visit));
for(i=1;i<=n;i++)
{
dis[i]=value[1][i];
}
visit[1]=true;
int mark;
double test=10000000000;
sum=0;
for(j=1;j<=n-1;j++)
{
test=INFINITE;
for(i=1;i<=n;i++)
{
if(visit[i]==false&&dis[i]<test)
{
test=dis[i];
mark=i;
}
}
sum+=test;visit[mark]=true;
for(i=1;i<=n;i++)
{
if(visit[i]==false&&value[mark][i]<dis[i])
dis[i]=value[mark][i];
}
}
return sum;
}
int main ()
{
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&dot[i].a,&dot[i].b);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
value[i][j]=distance(i,j);
}
}
printf("%.2f\n",prim());
system("pause");
return 0;
}