poj 1789 Truck History (mst,prim)
题意：其实题目不难理解。。。直接按照定义去搞就行了。。。
思路：由于距离在分母上。。所以要quality最大。。。就是要分母最小。。。
然后由于题目中说每一种类型的type只能由其他一种派生出来。。。我们可以把这个派生关系看做一条边。。。把每种类型看成点。。
这样就构成了一棵树。。。先o(nn7)预处理出权值。。。然后最小生成树即可。。。
这种给了坐标距离作为权值的图一定是稠密图。。。图小用kruskal糊弄一下就过去了。。。图大的话还是乖乖的用prim吧。。。
然而仍然 TLE???wtf??
最后发现。。因为我习惯用string...但是又怕卡cin...所以做法是scanf读入字符数组然后再赋值给string..
然而这种操作不知为何神tm慢。。。。。（求指教）
以至于：
要知道。。。这题时限2s啊。。。为毛能差1s多。。。也就是说时间的瓶颈完全是在读入了orz...
/* ***********************************************
Author :111qqz
Created Time :2016年07月14日 星期四 00时13分04秒
File Name :code/poj/1789.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2E3+7;
7int n,m;
8int f[N];
9int v[N];
10char st[N][10];
11//string st[N];
12int matrix[N][N];
1void init()
2{
3 for ( int i = 0 ; i < n; i++)
4 for ( int j = 0 ; j <n ; j++)
5 matrix[i][j] = inf;
6}
7int getw(char * a,char * b)
8{
9 int res = 0 ;
10 for ( int i = 0 ; i < 7 ; i++)
11 if (a[i]!=b[i]) res++;
12 return res;
13}
14void prim()
15{
16 bool flag[N];
17 int nearest[N];
18 int adjecent[N];
19 int i,j;
20 int min;
21 int sum=0;
1 for ( int i = 0 ; i < n ; i++) flag[i] = false;
2 flag[0] = true;
3 for(i = 1; i < n; ++i)
4 {
5 nearest[i] = matrix[0][i];
6 adjecent[i] = 0;
7 }
8 int count = n;
9 while(--count)
10 {
11 min = inf;
12 j = 0;
13 for(i = 0; i < n; ++i)
14 {
15 if(!flag[i] && nearest[i] < min)
16 {
17 min = nearest[i];
18 j = i;
19 }
20 }
21 sum+=matrix[j][adjecent[j]];
1 flag[j] = true;
2 for(i = 0; i < n; ++i)
3 {
4 if(!flag[i] && matrix[i][j] < nearest[i])
5 {
6 nearest[i] = matrix[i][j];
7 adjecent[i] = j;
8 }
9 }
10 }
11 printf("The highest possible quality is 1/%d.\n",sum);
12}
1int main()
2{
3#ifndef ONLINE_JUDGE
4 freopen("code/in.txt","r",stdin);
5#endif
1 while (~scanf("%d",&n))
2 {
3 if (n==0) break;
4 init();
1 for ( int i = 0 ; i < n ; i++)
2 {
3 // char tmp[10];
4 scanf("%s",st[i]);
5 // st[i]=tmp;
6 }
1 for ( int i = 0 ; i < n ; i++)
2 for ( int j = 0 ; j < n ; j++)
3 if (i<j)
4 {
matrix[i][j]=matrix[j][i]=getw(st[i],st[j]);
}
prim();
}
1#ifndef ONLINE_JUDGE
2 fclose(stdin);
3#endif
4 return 0;
5}