220
poj 1789 Truck History MST
prim
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int d[2001];
string org[2001];
bool vis[2001];
int n;
int prim()
{
int Min,now=0,i,k,K=n,ans=0,t;
while(K--)
{
Min=INF;
for(i=0;i<n;i++)
{
if(!vis[i]&&d[i]<Min)
{
Min=d[i];now=i;
}
}
vis[now]=1;
if(now)ans+=Min;
for(i=0;i<n;i++)
{
if(vis[i])continue;
t=0;
for(k=0;k<7;k++)
if(org[now][k]!=org[i][k])t++;
if(d[i]>t)d[i]=t;
}
}
return ans;
}
int main()
{
int i;
while(~scanf("%d",&n)&&n)
{
memset(vis,0,sizeof(vis));
memset(d,127,sizeof(d));
for(i=0;i<n;i++)
cin>>org[i];
printf("The highest possible quality is 1/%d.\n",prim());
}
}
最後更新：2017-04-04 07:03:45