POJ 1789 -- Truck History
Prim求分母的最小。即求最小生成树
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = + ;
const int INF = ;
int n;//有几个卡车
char str[maxn][];
int d[maxn];//记录编号的数值
int Edge[maxn][maxn];
int dist[maxn];
void prim()
{
int sum=;
//加入源点
dist[] = -;
for(int i=;i<n;i++)
{
dist[i] = Edge[][i];
} for(int i=;i<n;i++)//依次加入n-1条边
{
int min = INF,pos;
for(int j=;j<n;j++)//找出最小的一条
{
if(min>dist[j] && dist[j]!=-)
{
min = dist[j];pos = j;
}
}
//将pos加入
dist[pos] = -;sum+=min;
//进行路径的更新
for(int k=;k<n;k++)
{
if(dist[k] > Edge[pos][k])
dist[k]=Edge[pos][k];
}
}
cout<<"The highest possible quality is 1/"<<sum<<"."<<endl;
} int main()
{
while(cin>>n && n)
{
for(int i=;i<n;i++)
{
cin>>str[i];
}
for(int i=;i<n;i++)
{
int num=;
for(int k=;k<;k++)
num += (int)(str[i][k] - 'a');
d[i] = num;
}
memset(Edge,,sizeof(Edge));
for(int i=;i<n;i++)
{
for(int j=i+;j<n;j++)
{
int temp = ;
for(int k=;k<;k++)
{
temp += str[i][k]!=str[j][k];
}
Edge[i][j] = Edge[j][i] = temp;
}
}
memset(dist,INF,sizeof(dist));
prim(); } return ;
}