【HDU1162】Eddy's picture(MST基础题)

很基础的点坐标MST,一不留神就AC了, - - !!

 #include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <numeric>
#include <limits.h> #define typec double
using namespace std; const int inf = 0xffff;
const int V = ;
int vis[V];
typec lowc[V], Map[V][V], point[V][]; typec prim (typec cost[][V], int n) {
int i, j, p;
typec minc, res = ;
memset(vis, , sizeof(vis));
vis[] = ;
for (i = ; i < n; ++ i) lowc[i] = cost[][i];
for (i = ; i < n; ++ i) {
minc = inf;
p = -;
for (j = ; j < n; ++ j) {
if ( == vis[j] && minc > lowc[j]) {
minc = lowc[j];
p = j;
}
}
if (inf == minc) return -;
res += minc;
vis[p] = ;
for (j = ; j < n; ++ j) {
if ( == vis[j] && lowc[j] > cost[p][j]) {
lowc[j] = cost[p][j];
}
}
}
return res;
} double cal_dis (double x1, double y1, double x2, double y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
} int main () {
int n;
while (~scanf("%d", &n)) { for (int i = ; i < n; ++ i) {
scanf("%lf %lf", &point[i][], &point[i][]);
} for (int i = ; i < V; ++ i) {
for (int j = ; j < V; ++ j) {
if (i == j) Map[i][j] = ;
else Map[i][j] = inf;
}
} for (int i = ; i < n; ++ i) {
for (int j = i + ; j < n; ++ j) {
Map[i][j] = Map[j][i] =
cal_dis(point[i][], point[i][], point[j][], point[j][]);
}
} //cout << prim(Map, n) << endl;
printf("%.2lf\n", prim(Map, n));
}
return ;
}
上一篇:Autofac 的属性注入方式


下一篇:android:padding和android:margin的区别 详解