最小生成树(MinimumSpanningTree,MST)---Prim算法

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 103;
const int INF = 0x3f3f3f3f;    //最大值
int edge[MAXN][MAXN];        //邻接矩阵
int used[MAXN];         //标记这个点是否在最小生成树的集合(是否在T中)里面  0 代表未加入  1 代表加入
int lowcost[MAXN];      //存放的是未被加入集合的点(G中的点)到已经被加入集合的点(T中的点)的最短距离
int N,M;

int prim(int start,int maxn)    //假设 从 start 开始寻找MST， maxn  代表点的个数
{
   used[start] = 1;
   for(int i = 1; i <= maxn; i++)    //刚开始只有start 这个点在集合里面 所以初始化这个数组为到集合之外的各个点的距离 ，如果没有则是无穷大（INF）
   {
       lowcost[i] = edge[start][i];
   }
   int sumweight = 0;    // MST 的权值
   int ok = 0;
   for(int i = 1; i <= maxn; i++)
   {
       int minn = INF ;   //为找到最短的那条边
       int v = -1;          //标记找的那个点
       for(int j = 1; j <= maxn; j++)     //开始寻找集合之外得点到集合之里的点的最短边
       {
           if(used[j] == 0 && lowcost[j] //在集合之外的点寻找最短的边
           {
               minn = lowcost[j];
               v = j;  
           }
       }
       if(v != -1)    //找到了 v  这个点
       {
           ok++;
           used[v] = 1;   //标记已被使用
           sumweight += lowcost[v];   //更新权值
           for(int j = 1; j <= maxn; j++)      //更新存放最短边的集合(lowcost)
           {
               if(used[j] == 0 && lowcost[j] > edge[v][j])    //在集合之外(G)得点 寻找到集合之里(T)各个点的最短边 更新数组
               {
                   lowcost[j] = edge[v][j];
               }
           }
       }
   }
   if(ok == maxn -1)    //找到了
     return sumweight;
   return -1;     //没找到
}

int main()
{
    while(cin >> N >> M && N)
    {
        memset(edge, 0x3f, sizeof(edge));  //清空为最大值
        memset(used, 0, sizeof(used));    //刚开始所有的点都在集合之外
        while(N--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            edge[u][v] = edge[v][u] = w;
        }
        int ans = prim(1, M);       //从 1 这个点开始找 一共有M个点
        if(ans <0) cout <<"?" <<endl;
        else cout < endl;
    }
    return 0;
}

 1 const int MAXN = 10000; 
 2 const int MAXE = 100000;
 3 const int INF = 0x3f3f3f3f;
 4 int n, m;
 5 bool visit[MAXN + 3];
 6 int lowcost[MAXN + 3];
 7 int pre[MAXN + 3];
 8 
 9 int head[MAXN + 3], len;
10 struct EDGE { int to; int next; int w; };
11 EDGE edge[2 * MAXE + 3];
12 
13 void addedge(int u, int v, int w) { 
14     edge[len].to = v;
15     edge[len].w = w;
16     edge[len].next = head[u];
17     head[u] = len++;
18 }
19 
20 struct NODE { //队列中的节点
21     int v; int w; //点  v 到 MST 集合中的距离为 w
22     NODE () {}
23     NODE (int u, int wh) {v = u, w = wh;}
24     bool operator <(const NODE& a) const {
25         if(w == a.w) return v > a.v;
26         return w > a.w;
27     }
28     NODE& operator = (const NODE & a) {
29         v = a.v, w = a.w;
30         return *this;
31     }
32 };
33 
34 int prim(int st) {
35     memset(visit, false, sizeof(visit));
36     memset(pre, -1, sizeof(pre));
37     for(int i = 0; i <= n; i++) lowcost[i] = INF;
38     lowcost[st] = 0, pre[st] = st;
39     priority_queue minhp;
40     minhp.push( NODE(st, 0) );    //初始节点入队
41     int mst = 0, cnt = 0;
42     while( !minhp.empty() ) {
43         NODE tp = minhp.top(); minhp.pop(); //从队列首部取出最近的节点, 并删除
44         if(visit[tp.v]) continue;
45         visit[tp.v] = true; //标记已访问节点
46         mst += tp.w, cnt++;//记录MST权值以及MST集合中的点的个数
47         for(int k = head[tp.v], j; k != -1; k = edge[k].next) {
48             if(!visit[j = edge[k].to] && edge[k].w //更新最短边长度
49                 pre[j] = tp.v;
50                 lowcost[j] = edge[k].w;
51                 minhp.push( NODE(j, lowcost[j]) );
52             }
53         }
54     }
55     return cnt == n ?  mst : -1;
56 }