[图论算法]Prim算法

用prim算法实现最小生成树
可以在sicily上做1083

#include <iostream>
using namespace std;
#include <cstring>
#define INF 0x7fffffff
int n, map[101][101], minid, minlen;
// 最小生成树 -- prim算法 
int prim(){
    int lowcost[101], sum = 0;
    for (int i = 2; i <= n; ++i) {
        if (map[1][i] != 0)
            lowcost[i] = map[1][i]; // 先不管是不是0都放进来
        else 
            lowcost[i] = INF;
    } // 假设第一个点已经被选了。那么第i个点跟这个集合中的点最近的距离就是lowcast[i]
    for (int i=2; i <= n; ++i) {// 选剩下的其他点
        minid = minlen = INF; // 主要是将长度设置为无穷大（只能说是比较大而已）
        for (int j = 2; j <= n; ++j) {
            if (lowcost[j] != 0 && lowcost[j] < minlen) { // 为0表示已经被拿进来了
                minid = j;
                minlen = lowcost[j];
            }
        }
        sum += minlen; // 加上这个边之后的集合,同时把这个点放到点集中 
        for (int j = 2; j <= n; ++j) {
            if (lowcost[j] > map[minid][j] && map[minid][j] != 0) {
                lowcost[j] = map[minid][j];
            } // 这里map不能取0是由于main函数部分，不存在的边距离被设置为了0
        }
        lowcost[minid] = 0; // 标记距离最小的这个点已经被取走了
    }
    return sum;
} 
int main(){
    int m, x, y, cost;
    while (cin >> n && n){ // 输入点的个数 
        cin >> m;// 输入边的个数 
        memset(map, 0, sizeof(map)); // 初始化为0 
        for (int i = 0; i < m; ++i) {
            cin >> x>> y >> cost;
            if (map[x][y] == 0 || map[x][y] > cost) {
                map[y][x] = map[x][y] = cost; // 存储了每个点 
            }
        } // 输入 map[i][j] = 0 mean there is no way between i and j. 
        cout << prim()<< endl; 
    }
}