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

//prime算法是维护集合到点的最短距离
//迪杰斯特拉算法是维护点到点的最短距离

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAXN 110        //注意这是点的数目，prime算法可以忽略边数的多少,所以适合稠密图
#define INF 0x3f3f3f3f
int n, m;
int lowcost[MAXN];//lowcost数组保存现有的到j点的最短距离
int vis[MAXN];
int mp[MAXN][MAXN];

void init()
{
    memset(vis, 0, sizeof(vis));
    memset(lowcost, 0, sizeof(lowcost));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            mp[i][j] = INF;
        }
    }
}

void prime()
{
    int pos, ans;
    ans = 0;
    vis[1] = 1;
    for(int i = 1; i <= n; i++){//初始化到j点的最短的距离都是第一个节点到j点的距离
        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[pos][j])//如果没连通j点,且pos点到j点的距离小于现有的到j的最小距离,则更新lowcost数组
                lowcost[j] = mp[pos][j];
        }
    }
    printf("%d\n", ans);
}


int main()
{
    int tmp;
    while(scanf("%d", &n) != EOF){
        init();
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                scanf("%d", &tmp);
                if(tmp < mp[i][j])
                    mp[i][j] = tmp;
            }
        }
        prime();
    }
    return 0;
}
Contents