POJ 1789 Truck History G++
程序员文章站
2022-07-15 11:09:32
...
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
//英语 看博友分析
int fa[2008];
struct nod{
int zhi;
int x,y;
};
bool cmp(nod a, nod b)
{
return a.zhi<b.zhi;
}
int find(int a)
{
if(fa[a]==-1)
{
return a;
}else
{
return fa[a]=find(fa[a]);
}
}
int main()
{
while(1)
{
int n;
//cin>>n;
scanf("%d",&n);
if(n==0)
{
break;
}
memset(fa,-1,sizeof(int)*(n+1));
vector<string> ve;
vector<nod> da;
for(int i=0;i<n;i++)
{
char s[100];
scanf("%s",s);
string ts=s;
ve.push_back(ts);
}
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
int js=0;
for(int k=0;k<7;k++)
{
if(ve[i][k]!=ve[j][k])
{
js++;
}
}
nod t;
t.x=i;
t.y=j;
t.zhi=js;
da.push_back(t);
}
}
sort(da.begin(),da.end(),cmp);
int jg=0;
for(int i=0;i<da.size();i++)
{
int tx=da[i].x;
int ty=da[i].y;
int tz=da[i].zhi;
tx=find(tx);
ty=find(ty);
if(tx!=ty)
{
fa[tx]=ty;
jg=jg+tz;
}
}
printf("The highest possible quality is 1/%d.\n",jg);
//cout<<"The highest possible quality is 1/"<<jg<<"."<<endl;
}
return 0;
}
上一篇: 关闭MacOS中的启动项
下一篇: Redis——进阶篇