POJ1789TruckHistory

2012年的最后一天。刚刚又A了一道题。留作纪念 题意大概是给你N个字符串,串长度为7。每个串都可以由其他串变化而来 其代价是两个串中对应位置不同字母的个数。寻找一种方案是代价最小

我们把每个串看成一个点。构建一个图。图的边的权值就是两个串之间不同字母的数目 用prim算法求的最小生成树既可!

//poj 1789 最小生成树
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define MAX 2010
int mm[MAX][MAX];
char ss[MAX][9];
int vis[MAX];
int dis[MAX];
int n;
//求两字符串不同字母数目
int diff(char *s1,char *s2)
{
    int cc=0;
    for(int i=0;s1[i]!='\0';i++)
    {
        if(s1[i]!=s2[i])
            cc++;
    }
    return cc;
}
//prim算法实现过程
int prim()
{
    int s=0,sum=1,i,j;//s为起始点,sum为最小生成树顶点个数
    int min,minp,ans=0;//ans为最小生成树长度
                       //min新加入点到其他点的最短路
    memset(vis,0,sizeof(vis));
    for(i=0;i<MAX;i++)
        dis[i]=MAX;
    vis[s]=1;
    while(1)
    {
        if(sum==n) break;//sum==n表示所有点都加入了生成树,break
        min=MAX;        
        for(j=1;j<n;j++)
        {
            if(!vis[j] && dis[j]>mm[s][j])//更新s点到其他顶点距离
                dis[j]=mm[s][j];
            if(!vis[j] && dis[j]<min)//寻找一个最短路径
            {
                min=dis[j];
                minp=j;
            }
        }
        s=minp;
        vis[s]=1;
        sum++;
        ans+=min;
    }
    return ans;
}
int main()
{
    int i,j;
    while(scanf("%d",&n)&&n)
    {
        for(i=0;i<n;i++)
            scanf("%s",ss[i]);
        for(i=0;i<n;i++)
        {
            mm[i][i]=0;
            for(j=i+1;j<n;j++)
            {
                mm[i][j]=mm[j][i]=diff(ss[i],ss[j]);
                //计算权值,即两个串之间不同字母的数目
            }
        }
        printf("The highest possible quality is 1/%d.\n",prim());
    }
    return 0;
}