英语考试 (最小生成树)

素颜马尾好姑娘i 2022-06-09 01:36 86阅读 0赞

在过三个礼拜，YellowStar有一场专业英语考试，因此它必须着手开始复习。

这天，YellowStar准备了n个需要背的单词，每个单词的长度均为m。

YellowSatr准备采用联想记忆法来背诵这n个单词：

1、如果YellowStar凭空背下一个新词T，需要消耗单词长度m的精力

2、如果YellowSatr之前已经背诵了一些单词，它可以选择其中一个单词Si，然后通过联想记忆的方法去背诵新词T，需要消耗的精力为hamming(Si, T) \* w。

hamming(Si, T)指的是字符串Si与T的汉明距离，它表示两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。

由于YellowStar还有大量繁重的行政工作，因此它想消耗最少的精力背诵下这n个单词，请问它最少需要消耗多少精力。

Input

包含多组测试数据。

第一行为n, m, w。

接下来n个字符串，每个字符串长度为m，每个单词均为小写字母'a'-'z'组成。

1≤n≤1000

1≤m, w≤10

Output

输出一个值表示答案。

Sample Input

3 4 2
    abch
    abcd
    efgh

Sample Output

转换成最小生成树来做，难以想到

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define inf 0x3f3f3f3f
    int map1[1005][1005];
    int vis[1005];
    int dis[1005];
    int n,m,w;
    void prim()
    {
        for(int i=1; i<n; i++)
            dis[i]=map1[0][i];
        dis[0]=0;
        vis[0]=1;
        int ans=0;
        for(int i=0; i<n-1; i++)
        {
            int minn=inf,temp;
            for(int j=0; j<n; j++)
            {
                if(!vis[j]&&dis[j]<minn)
                {
                    minn=dis[j];
                    temp=j;
                }
            }
            vis[temp]=1;
            ans+=minn;
            for(int j=0; j<n; j++)
            {
                if(!vis[j]&&dis[j]>map1[temp][j])
                {
                    dis[j]=map1[temp][j];
                }
            }
        }
        printf("%d\n",ans+m);
    }
    int main()
    {
        char str[1005][15];
        while(~scanf("%d%d%d",&n,&m,&w))
        {
            memset(map1,0,sizeof(map1));
            for(int i=0; i<n; i++)
                scanf("%s",str[i]);
            for(int i=0; i<n-1; i++)
            {
                for(int j=i+1; j<n; j++)
                {
                    int s=0;
                    for(int k=0; k<m; k++)
                        if(str[i][k]!=str[j][k])
                            s++;
                    map1[i][j]=map1[j][i]=min(m,s*w);
                }
            }
            memset(vis,0,sizeof(vis));
            prim();
        }
        return 0;
    }