杭电oj-1233-还是畅通工程

题目链接：还是畅通工程
prim算法原理
注意点：本文针对的题目还是畅通工程中每两个顶点间都是有一条非零的连接，即共n（n-1）/2条边，且都不为0.如果遇到有两个顶点间无连接的情况且题目初始为0，对于这种情况，需要在输入出将无连接的两点之间的距离初始化为无穷大，这样才不会影响在寻找最小边和更新较小值时出错。本题由于两两都有连接故无需进行初始化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
int n;
int graph[101][101];

int prim(int n){
    //lowcost记录未加入最小生成树的顶点到生成树中所有顶点的距离中的最小距离 ，如果已经加入生成树集合，则将其值记为0 
    int lowcost[101];
    //lowcost最小距离边的两个顶点a,b， 会有一个在最小生成树顶点集合中，假设是a， 另一个不在其中，假设为b
    //mst则记录的是最小距离边在最小生成树中对应的顶点a ，记录形式为mst[b]=a ，即b指向a 
    int mst[101];
    int min, minid, sum = 0, i, j;
    //初始化lowcost和mst，一般默认是从顶点1开始，即假设最小生成树最开始的起点为1，可以换其他顶点，结果一样，
    //则初始化其他顶点到最小生成树的最小距离，因为只有顶点1，所以就是结点i到结点1的距离，相应的mst中结点i指向结点1 
    for(i = 2; i <= n; i++){
        lowcost[i] = graph[i][1];
        mst[i] = 1;
    }
    //初始将1加入最小生成树顶点集合 
    mst[1] = 0;
    for(i = 2; i <= n; i++){
        //最小值初始化，定义为最大，方便比较 
        min = 0x7fffffff;
        //初始化最小值指向的id 
        minid = 0;
        //寻找最小值，1结点已经在最小生成树中，则从2开始 
        for(j = 2; j <= n; j++){
            //边权值较小且不在生成树中
            if(lowcost[j] < min && lowcost[j] != 0){
                min = lowcost[j];
                minid = j;
            }
        }
        //累加权值
        sum += min;
        //标记节点minid加入生成树
        lowcost[minid] = 0;
        //由于新添加了一个顶点到最小生成树，所以可能其他点通过该点连接到最小生成树的距离会更小，所以需要更新不在最小生成树中的顶点到最小生成树的最小距离 
        for(j = 2; j <= n; j++){
            //发现更小的权值
            if(graph[j][minid] < lowcost[j]){
                //更新权值信息
                lowcost[j] = graph[j][minid];
                //更新最小权值边的起点
                mst[j] = minid;
            }
        }
    }
    //返回最小权值和
    return sum;
}



int main()
{
    int i, a, b, ans, dis;
    while(scanf("%d", &n) && n != 0){
        for(i = 1; i <= n*(n-1)/2; i++){
            scanf("%d%d%d", &a, &b, &dis);
            //本题是无向图，所以需要对称设置其距离 
            graph[a][b] = dis;
            graph[b][a] = dis;
        }
        ans = prim(n);
        printf("%d\n", ans);
    }
    return 0;
}