MST问题。
以下是我的代码：
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
const int kMaxn(2007);
const int kInf(0x7f7f7f7f);
int n,g[kMaxn][kMaxn];
string name[kMaxn];
int mst,lowcost[kMaxn];
int dist(int a,int b)
{
int re(0);
for(int i=0;i<7;i++)
if(name[a][i]!=name[b][i])
re++;
return re;
}
void Prim()
{
mst=0;
for(int i=1;i<=n;i++)
lowcost[i]=g[1][i];
lowcost[1]=-1;
for(int i=1;i<=n-1;i++)
{
int v(-1),w(kInf);
for(int j=1;j<=n;j++)
if(lowcost[j]!=-1 && w>lowcost[j])
{
v=j;
w=lowcost[j];
}
if(v!=-1)
{
mst+=w;
lowcost[v]=-1;
for(int j=1;j<=n;j++)
if(lowcost[j]!=-1 && lowcost[j]>g[v][j])
lowcost[j]=g[v][j];
}
}
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(cin>>n && n)
{
for(int i=1;i<=n;i++)
cin>>name[i];
for(int i=2;i<=n;i++)
for(int j=1;j<=i-1;j++)
g[i][j]=g[j][i]=dist(i,j);
Prim();
printf("The highest possible quality is 1/%d.\n",mst);
}
return 0;
}
posted on 2011-07-31 09:41
lee1r 阅读(219)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论