POJ 1789 C++ （图论）

//题目意思难懂
//其实就是求最小生成树，用经典的prim算法
#include<iostream>
using namespace std;
int  array[2001][2001],total;
int  used[2001],dis[2001];
char truck[2001][8];
void prim(int n)
{ int v,min;
  for(int i=1;i<=n;i++)
      {used[i]=0;
       dis[i]=array[1][i];
       }
       used[1]=1;
      while(true)
        {  min=INT_MAX;
            v=0;
            for(int i=1;i<=n;i++)
               if(!used[i] && dis[i]<min) //在S的补集选出权最小的边
                 { min=dis[i];
                   v=i;
                  }
            if(v==0)
               break;
           total=total+min;
           used[v]=1; //加入S集合
           for(int j =1;j<=n;j++)
               if(!used[j] && dis[j]>array[v][j]) //更新最小权边的值
                   dis[j]=array[v][j];
        }  
  }                  

int main()
{int n,sum;
      freopen("in.txt","r",stdin);
      freopen("out.txt","w",stdout);
while(scanf("%d",&n),n!=0)
      {for(int i=1;i<=n;i++)
           scanf("%s",truck[i]);
        memset(array,0,sizeof(array));
        for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++)
               { if(i==j || array[i][j])
                    continue;
                  sum=0;  
                  for(int k=0;k<7;k++)
                      if(truck[i][k]!=truck[j][k])
                         sum++;
                   array[i][j]=sum;
                   array[j][i]=sum;
                }  
      total=0;
      prim(n);
      printf("The highest possible quality is 1/%d.\n",total);

  }  
  return 0;
}    

posted on 2008-11-27 00:13 蜗牛 阅读(393) 评论(0)  编辑 收藏 引用 所属分类: ACM ICPC