Coder Space

PKU 1789 Truck History--- 最小生成树，Prim算法

简单的最小生成树问题。
两个code的距离为对应位置字符不相同的个数，构造距离矩阵。
Prim算法求解。最小生成树的路径总长的倒数即为所求。

  1#include<iostream>
  2#include<limits>
  3
  4using namespace std;
  5
  6const int maxN = 2005;
  7const int INF = numeric_limits<int>::max();
  8
  9int G[maxN][maxN];
 10char code[maxN][10];
 11
 12//两个code的距离
 13int Distance(char c1[], char c2[])
 14{
 15    int cnt = 0;
 16    for(int i=0; i<7; i++)
 17    {
 18        if(c1[i] != c2[i])
 19        {
 20            cnt++;
 21        }
 22    }
 23    return cnt;
 24}
 25
 26//Prim算法求最小生成树
 27int Prim(int n)
 28{
 29    /*
 30    设S为已加入生成树中的点集，V-S为未加入的点集。对于V-S中的任一结点j，closest[j]是j在S中的一个邻接顶点，它与j具有最小的距离,lowest[j]即为此最小距离值。
 31    */
 32    int lowcost[maxN];
 33    //int closest[maxN];
 34    bool flag[maxN];
 35
 36    flag[1] = true;
 37
 38    //初始化
 39    for(int i=2; i<=n; i++)
 40    {
 41        lowcost[i] = G[1][i];
 42        //closest[i] = 1;
 43        flag[i] = false;
 44    }
 45
 46    for(int i=1; i<n; i++)
 47    {
 48        int temp = INF;
 49        int v = 1;
 50
 51        //搜索下一条最短边加入生成树
 52        for(int j=2; j<=n; j++)
 53        {
 54            if((!flag[j]) && (lowcost[j] < temp))
 55            {
 56                temp = lowcost[j];
 57                v = j;
 58            }
 59        }
 60        flag[v] = true;
 61
 62        //更新closest[]与lowcost[]数组
 63        for(int j=2; j<=n; j++)
 64        {
 65            if((!flag[j]) && (G[v][j] < lowcost[j]))
 66            {
 67                lowcost[j] = G[v][j];
 68                //closest[j] = v;
 69            }
 70        }
 71    }
 72
 73    int sumLen = 0;
 74    for(int i=2; i<=n; i++)
 75    {
 76        sumLen += lowcost[i];
 77    }
 78    return sumLen;
 79}
 80
 81int main()
 82{
 83    int N;
 84
 85    int i,j;
 86
 87    cin>>N;
 88    while(N!=0)
 89    {
 90        for(i=1; i<=N; i++)
 91        {
 92            cin>>code[i];
 93        }
 94
 95        for(i=1; i<=N; i++)
 96        {
 97            G[i][i] = 0;
 98            for(j=i+1; j<=N; j++)
 99            {
100                int d = Distance(code[i],code[j]);
101                G[i][j] = d;
102                G[j][i] = d;
103            }
104        }
105
106        cout<<"The highest possible quality is 1/"<<Prim(N)<<"."<<endl;
107
108        cin>>N;
109    }
110    return 0;
111}

posted on 2010-05-13 11:04 David Liu 阅读(221) 评论(0)  编辑 收藏 引用 所属分类: 图论


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


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论