【FZU - 2254】英语考试（最小生成树，思维，建图）

题干：

在过三个礼拜，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

10

Hint

最优方案是：先凭空记下abcd和efgh消耗精力8,在通过abcd联想记忆去背诵abch，汉明距离为1,消耗为1 * w = 2,总消耗为10。

解题报告：

  这题巧就巧在字符串是相同长度的，所以新开一个单词的代价都是同一个m，不然就不好处理了。最后再加上一个起始m就是答案。因为构成了一个完全图，所以prim算法肯定更快一些。这里就不管那些了。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e6 + 5; int f[MAX]; int n,m,w; char s[1005][55]; struct Edge {int u,v;int w; } e[MAX]; bool cmp(Edge a,Edge b) {return a.w < b.w; } int getf(int v) {return v == f[v] ? v : f[v] = getf(f[v]); } void merge(int u,int v) {int t1 = getf(u);int t2 = getf(v);f[t2] = t1; } int hamming(int x,int y) {int res = 0;for(int i = 0; i<m; i++) {res += s[x][i] != s[y][i]; }return res; } int main() {while(~scanf("%d%d%d",&n,&m,&w)) {int tot = 0;for(int i = 1; i<=n*n; i++) f[i] = i;for(int i = 1; i<=n; i++) scanf("%s",s[i]);for(int i = 1; i<=n; i++) {for(int j = i+1; j<=n; j++) {e[++tot].u = i;e[tot].v = j;e[tot].w = min(w*hamming(i,j),m);}}int ans = 0;sort(e+1,e+tot+1,cmp);for(int u,v,i = 1; i<=tot; i++) {u = e[i].u,v = e[i].v;if(getf(u) != getf(v)) {merge(u,v);ans += e[i].w;}}printf("%d\n",m + ans); }return 0 ; }

 

总结

以上是生活随笔为你收集整理的【FZU - 2254】英语考试（最小生成树，思维，建图）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。