prim模板题

题目链接:http://acm.hrbeu.edu.cn/index.php?act=problem&id=1223

 #include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector> #define maxn 115
using namespace std; const int INF = 0x3f3f3f; struct Point{
double x,y;
bool operator < (const Point & rh) const{
return y < rh.y || (y == rh.y && x < rh.x);
}
}p[maxn];
int n;
double ans;
double G[maxn][maxn]; double calculate(int i,int j){
double xx = p[j].x - p[i].x;
double yy = p[j].y - p[i].y;
return sqrt(xx*xx + yy*yy);
} void prim(){
bool vis[maxn];
double lowdist[maxn];
double mindist;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++) lowdist[i]=INF;
int point;
int s=;
vis[s] =true;
int num=;
while(true){
if(num == n) break;
vis[s]=true;
mindist = INF;
for(int i=;i<=n;i++){
if(!vis[i] && lowdist[i] > G[s][i]){
lowdist[i] = G[s][i];
}
if(!vis[i] && mindist > lowdist[i]){
mindist=lowdist[i];
point = i;
}
}
s = point;
ans += mindist;
num++;
}
return;
}
int main()
{
// if(freopen("input.txt","r",stdin)== NULL) {printf("Error\n"); exit(0);} while(scanf("%d",&n)== && n){
for(int i=;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++){
G[i][j] = G[j][i] = calculate(i,j);
}
ans = ;
//print();
prim();
printf("%.2lf\n",ans);
}
}
上一篇:Android学习笔记_58_清除手机应用程序缓存


下一篇:三十项调整助力 Ubuntu 13.04 更上一层楼