1 思路

。

最小生成树（MST）问题。

2 代码

代码来自。

#include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=2001;char    c[N][8];                // 保存字符串int     m[N][N];                // m[i][j]第i个结点与第j个结果之间权值int     d[N];                   // 遍历时存储最小值bool    v[N];                   // 遍历时存储结点是否被访问过int     n;// 比较字符串返回路径权值int cmp(int a, int b){    int n = 0;    for(int i=0; i<7; i++)        if(c[a][i] != c[b][i])            n ++;    return n;}//Prim算法void prim(){    int i, j;    for(i=1; i<=n; i++)         // 把第1个结点所有邻结点的路径保存在d中        d[i] = m[1][i];    memset(v, 0, sizeof(v));    int ans=0;    while(1){        int mark = -1;        int min = numeric_limits
          
           ::max();        for(i=1; i<=n; i++)            if(!v[i] && min>d[i]){ // 找到最短的路径，结点保存在mark中，权值保存在min中                min = d[i];     mark = i;            }        if(mark == -1){            // mark==-1表明经历上面的for循环后mark没有变化，说明所有的结点都已经访问过（v中标记也所有的结点）            cout<<"The highest possible quality is 1/"<
           
            <<"."<
            
             m[mark][i]) d[i] = m[mark][i]; }}// readvoid read(){ int i, j; while(cin>>n){ if(!n) return; for(i=1; i<=n; i++) cin>>c[i]; for(i=1; i<=n; i++) for(j=i+1; j<=n; j++){ m[i][j] = cmp(i, j); // 保存权值 m[j][i] = m[i][j]; } prim(); }}int main(int argc, char *argv[]){ read(); return 0;}
            
           
          
         
        
       

Author: visaya fan 

Date: 2011-08-24 12:55:48

HTML generated by org-mode 6.33x in emacs 23