Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：其实题目不难理解。。。直接按照定义去搞就行了。。。
思路：由于距离在分母上。。所以要quality最大。。。就是要分母最小。。。
然后由于题目中说每一种类型的type只能由其他一种派生出来。。。我们可以把这个派生关系看做一条边。。。把每种类型看成点。。
这样就构成了一棵树。。。先o(nn7)预处理出权值。。。然后最小生成树即可。。。
这种给了坐标距离作为权值的图一定是稠密图。。。图小用kruskal糊弄一下就过去了。。。图大的话还是乖乖的用prim吧。。。
然而仍然 TLE???wtf??
最后发现。。因为我习惯用string…但是又怕卡cin…所以做法是scanf读入字符数组然后再赋值给string..
然而这种操作不知为何神tm慢。。。。。（求指教）
以至于：[
要知道。。。这题时限2s啊。。。为毛能差1s多。。。也就是说时间的瓶颈完全是在读入了orz…
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月14日 星期四 00时13分04秒
4File Name :code/poj/1789.cpp
5 ************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=2E3+7;
34int n,m;
35int f[N];
36int v[N];
37char st[N][10];
38//string st[N];
39int matrix[N][N];
40
41void init()
42{
43 for ( int i = 0 ; i < n; i++)
44 for ( int j = 0 ; j <n ; j++)
45 matrix[i][j] = inf;
46}
47int getw(char * a,char * b)
48{
49 int res = 0 ;
50 for ( int i = 0 ; i < 7 ; i++)
51 if (a[i]!=b[i]) res++;
52 return res;
53}
54void prim()
55{
56 bool flag[N];
57 int nearest[N];
58 int adjecent[N];
59 int i,j;
60 int min;
61 int sum=0;
62
63 for ( int i = 0 ; i < n ; i++) flag[i] = false;
64 flag[0] = true;
65 for(i = 1; i < n; ++i)
66 {
67 nearest[i] = matrix[0][i];
68 adjecent[i] = 0;
69 }
70 int count = n;
71 while(--count)
72 {
73 min = inf;
74 j = 0;
75 for(i = 0; i < n; ++i)
76 {
77 if(!flag[i] && nearest[i] < min)
78 {
79 min = nearest[i];
80 j = i;
81 }
82 }
83 sum+=matrix[j][adjecent[j]];
84
85 flag[j] = true;
86 for(i = 0; i < n; ++i)
87 {
88 if(!flag[i] && matrix[i][j] < nearest[i])
89 {
90 nearest[i] = matrix[i][j];
91 adjecent[i] = j;
92 }
93 }
94 }
95 printf("The highest possible quality is 1/%d.\n",sum);
96}
97
98int main()
99{
100#ifndef ONLINE_JUDGE
101 freopen("code/in.txt","r",stdin);
102#endif
103
104 while (~scanf("%d",&n))
105 {
106 if (n==0) break;
107 init();
108
109 for ( int i = 0 ; i < n ; i++)
110 {
111 // char tmp[10];
112 scanf("%s",st[i]);
113 // st[i]=tmp;
114 }
115
116 for ( int i = 0 ; i < n ; i++)
117 for ( int j = 0 ; j < n ; j++)
118 if (i<j)
119 {
120
121 matrix[i][j]=matrix[j][i]=getw(st[i],st[j]);
122
123 }
124
125 prim();
126 }
127
128#ifndef ONLINE_JUDGE
129 fclose(stdin);
130#endif
131 return 0;
132}