By yusijia

Updated:

Contents 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

分析：
1 由于点有1000，如果要用kruskal的话最少有1000000条边，所以我么选择用prim算法
2 题目中的点的坐标最大值为10^6，那么如果在平方一下的话会超过int，所以在求两个
点之间的距离的时候用在前面乘上一个1.0这样就表示的double从而不会超过int了。
3 题目中的说了，要用64位的浮点数，所以选择用double 。输出的时候是“%0.2Lf”，不知道为啥long double才能过



#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAXN 1010        //注意这是点的数目，prime算法可以忽略边数的多少,所以适合稠密图
#define INF 0x3f3f3f3f

int n, m;
int vis[MAXN];
long double mp[MAXN][MAXN];
long double lowcost[MAXN];//lowcost数组保存现有的到j点的最短距离

struct Point{
    int x;
    int y;
}p[MAXN];

void init()
{
    long double tmp_x, tmp_y;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            tmp_x = 1.0 * (p[i].x - p[j].x) * (p[i].x - p[j].x);/*这里注意乘上一个1.0*/
            tmp_y = 1.0 * (p[i].y - p[j].y) * (p[i].y - p[j].y);/*这里注意乘上一个1.0*/
            mp[i][j] = sqrt(tmp_x + tmp_y);
        }
    }
}

void prime()
{
    int pos;
    long double ans = 0.0;
    memset(vis, 0, sizeof(vis));
    vis[1] = 1;
    for(int i = 1; i <= n; i++){
        lowcost[i] = mp[1][i];
    }
    for(int i = 1; i <= n; i++){
        pos = -1;
        for(int j = 1; j <= n; j++)if(!vis[j] && (pos == -1 || lowcost[j] < lowcost[pos])){
            pos = j;
        }
        if(pos == -1)
            break;
        ans += lowcost[pos];
        vis[pos] = 1;
        for(int j = 1; j <= n; j++)if(!vis[j] && lowcost[j] > mp[j][pos]){
            lowcost[j] = mp[j][pos];
        }
    }
    printf("%0.2lf\n", ans);
}

int main()
{
    int x, y;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &p[i].x, &p[i].y);
    }
    init();
    for(int j = 1; j <= m; j++){
        scanf("%d%d", &x, &y);
        mp[x][y] = mp[y][x] = 0;//把已经修好的路长度算0
    }
    prime();
    return 0;
}
Contents