Coder Space

PKU 1251 Jungle Roads--- 最小生成树，Prim算法

简单的最小生成树问题，Prim算法求解。

  1/*
  2简单的最小生成树问题，Prim算法。
  3*/
  4
  5#include<iostream>
  6#include<queue>
  7
  8using namespace std;
  9
 10const int maxN = 27;
 11
 12//边结构
 13struct Edge
 14{
 15    int e;
 16    int w;
 17    Edge *next;
 18
 19    bool operator < (const Edge &edge) const      //重载运算符，注意优先级队列中<，>号
 20    {
 21        return w > edge.w;
 22    }
 23};
 24
 25Edge *G[maxN];
 26
 27void AddEdge(int u, int v, int w)
 28{
 29    Edge *ptr = new Edge;
 30    ptr->e = v;
 31    ptr->w = w;
 32    ptr->next = G[u];
 33    G[u] = ptr;
 34}
 35
 36//Prim算法求最小生成树
 37int Prim(int n, int s)
 38{
 39    bool flag[maxN];
 40    priority_queue<Edge> q;
 41
 42    int minLen = 0;
 43
 44    Edge cur;
 45
 46    for(int i=1; i<=n; i++)
 47    {
 48        flag[i] = false;
 49    }
 50    flag[s] = true;
 51
 52    for(Edge *ptr = G[s]; ptr != NULL; ptr = ptr->next)
 53    {
 54        q.push(*ptr);
 55    }
 56
 57    while(!q.empty())
 58    {
 59        cur = q.top();
 60        q.pop();
 61
 62        if(!flag[cur.e])
 63        {
 64            flag[cur.e] = true;
 65            minLen += cur.w;
 66
 67            for(Edge *ptr = G[cur.e]; ptr != NULL; ptr = ptr->next)
 68            {
 69                if(!flag[ptr->e])
 70                {
 71                    q.push(*ptr);
 72                }
 73            }
 74        }
 75    }
 76    return minLen;
 77}
 78
 79int main()
 80{
 81    int n;
 82    char lab;
 83    int u,v,w;
 84    int k;
 85
 86    int i,j;
 87
 88    cin>>n;
 89    while(n!=0)
 90    {
 91        for(i=1;i<=n;i++)
 92        {
 93            G[i] = NULL;
 94        }
 95
 96        for(i=1;i<n;i++)
 97        {
 98            cin>>lab;
 99            u = lab - 'A' + 1;
100            cin>>k;
101            for(j=0;j<k; j++)
102            {
103                cin>>lab;
104                v = lab - 'A' + 1;
105                cin>>w;
106                AddEdge(u,v,w);
107                AddEdge(v,u,w);
108            }
109        }
110
111        cout<<Prim(n,1)<<endl;
112
113        cin>>n;
114    }
115}
116

posted on 2010-05-12 01:48 David Liu 阅读(207) 评论(0)  编辑 收藏 引用 所属分类: 图论


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论