英语考试(最小生成树)

Problem 2254 英语考试

Accept: 35 Submit: 72
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

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

Hint

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

Source

福州大学第十四届程序设计竞赛_重现赛

//没想到额,是最小生成树，首先想到的竟然是贪心解决，后来发现这样显然错误，决定哪些直接记住的很关键。

对于每个单词，可以直接记忆，也可以通过任何一个单词联想记忆，所以，想到这，可以想到似乎是个完全图，边的值为min(m,hamming(Si, T)*w)

然后就跑最小生成树

kruskal

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string.h>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 #define INF 0x3f3f3f3f
 8 #define MX 1005
 9 struct Node
10 {
11     int u,v;
12     int d;
13     bool operator < (const Node &b)const{
14         return d>b.d;
15     }
16 };
17 int n,m,w;
18 char str[MX][15];
19 priority_queue<Node> Q;
20 int f[MX];
21 
22 int find_h(int x){
23     if (x!=f[x])
24         f[x]=find_h(f[x]);
25     return f[x];
26 }
27 
28 void krus()
29 {
30     for (int i=0;i<n;i++)
31         f[i]=i;
32     int res = m; //star at 0
33     int num=1;
34     while (!Q.empty())
35     {
36         Node tp = Q.top();
37         Q.pop();
38         int x=find_h(tp.u),y=find_h(tp.v);
39         if (x!=y)
40         {
41             res+=tp.d;
42             f[x]=y;
43             num++;
44         }
45         if (num==n) break;
46     }
47     printf("%d
",res);
48 }
49 
50 int main()
51 {
52     while (scanf("%d%d%d",&n,&m,&w)!=EOF)
53     {
54         for (int i=0;i<n;i++)
55             scanf("%s",str[i]);
56         while (!Q.empty()) Q.pop();
57         for (int i=0;i<n;i++)
58         {
59             for (int j=i+1;j<n;j++)
60             {
61                 if (i==j) continue;
62                 int cp=0;
63                 for (int k=0;k<m;k++)
64                     if (str[i][k]!=str[j][k])
65                         cp++;
66                 Q.push((Node){i,j,min(m,cp*w)});
67             }
68         }
69         krus();
70     }
71     return 0;
72 }

View Code

prim

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string.h>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 #define INF 0x3f3f3f3f
 8 #define MX 1005
 9 struct Node
10 {
11     int u,v;
12     int d;
13     bool operator < (const Node &b)const{
14         return d>b.d;
15     }
16 };
17 int n,m,w;
18 char str[MX][15];
19 int G[MX][MX];
20 int vis[MX];
21 int dis[MX];
22 
23 void prim()
24 {
25     memset(vis,0,sizeof(vis));
26     vis[0]=1;
27     for (int i=0;i<n;i++)
28         dis[i]=G[0][i];
29     int num=1,sp=m;
30     while (num<n)
31     {
32         int mim=INF,dex;
33         for (int i=0;i<n;i++)
34             if (!vis[i]&&dis[i]<mim)
35         {
36             dex=i;
37             mim=dis[i];
38         }
39         vis[dex]=1;
40         sp+=mim;
41         num++;
42         for (int i=0;i<n;i++)
43             if (!vis[i]&&dis[i]>G[dex][i])
44                 dis[i]=G[dex][i];
45     }
46     printf("%d
",sp);
47 }
48 
49 int main()
50 {
51     while (scanf("%d%d%d",&n,&m,&w)!=EOF)
52     {
53         for (int i=0;i<n;i++)
54             scanf("%s",str[i]);
55         for (int i=0;i<n;i++)
56         {
57             for (int j=0;j<n;j++)
58             {
59                 if (i==j) continue;
60                 int cp=0;
61                 for (int k=0;k<m;k++)
62                     if (str[i][k]!=str[j][k])
63                         cp++;
64                 G[i][j]=G[j][i]=min(m,cp*w);
65             }
66         }
67         prim();
68     }
69     return 0;
70 }

View Code