Truck History--poj1789
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 21534 | Accepted: 8379 |
Description
Today, ACM is rich enough to pay historians to study its history. One thing historians tried to find out is so called derivation plan -- i.e. how the truck types were derived. They defined the distance of truck types as the number of positions with different letters in truck type codes. They also assumed that each truck type was derived from exactly one other truck type (except for the first truck type which was not derived from any other type). The quality of a derivation plan was then defined as
1/Σ(to,td)d(to,td)
where the sum goes over all pairs of types in the derivation plan such that to is the original type and td the type derived from it and d(to,td) is the distance of the types.
Since historians failed, you are to write a program to help them. Given the codes of truck types, your program should find the highest possible quality of a derivation plan.
Input
Output
Sample Input
4
aaaaaaa
baaaaaa
abaaaaa
aabaaaa
0
Sample Output
The highest possible quality is 1/3. 这题,我是没看懂,后来看的别人的翻译才自己做的!
>
> 例如有如下4个编号:
>
> aaaaaaa
>
> baaaaaa
>
> abaaaaa
>
> aabaaaa
>
> 显然的,第二,第三和第四编号分别从第一编号衍生出来的代价最小,因为第二,第三和第四编号分别与第一编号只有一个字母是不同的,相应的distance都是1,加起来是3。也就是最小代价为3。
显然,最小生成树!
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int per[],n;
struct node
{
int b,e,w;
}s[];//我开的挺大的,怕不够
bool cmp(node x,node y)
{
return x.w<y.w;
}
void init()
{
for(int i=;i<=n;i++)
per[i]=i;
}
int find(int x)
{
int i=x,j;
while(x!=per[x])
x=per[x];
while(i!=x)//我压缩了路径踩过的,超时了好多次
{
j=per[i];
per[i]=x;
i=j;
}
return x;
}
bool join(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
{
per[fx]=fy;
return true;
}
return false;
}
int main()
{
char map[][];
while(scanf("%d",&n),n)
{
getchar();
init();
int i,j;
for(int i=;i<n;i++)
scanf("%s",map[i]);
int k=,sum=,t;
for(i=;i<n;i++)
{
for(j=i+;j<n;j++)
{
int cot=;
for(t=;t<;t++)
{
if(map[i][t]!=map[j][t])
cot++;
}
s[k].b=i;
s[k].e=j;
s[k].w=cot;
k++;
}
}
sort(s,s+k,cmp);
for(i=;i<k;i++)
{
if(join(s[i].b,s[i].e))
sum+=s[i].w;
}
printf("The highest possible quality is 1/%d.\n",sum);
}
return ;
}
欢迎留言。
最新文章
- [转] js实现html table 行,列锁定
- 51nod1085(01背包)
- 【转】Crontab定时任务配置
- AC日记——石头剪子布 openjudge 1.7 04
- 隐匿在iOS文件系统中的隐私信息
- centos6.6下编译安装mysql5.6之后启动失败:Starting MySQL... ERROR! The server quit without updating PID file (/var/lib/mysql/localhost.localdomain.pid).
- Docker 使用指南 (六)—— 使用 Docker 部署 Django 容器栈
- libGraphicsMagickWand.so: cannot open shared object file: No such file or directory stack traceback:
- CygWin模拟Linux环境进行Ant批量打包
- HIbernate学习笔记(八) hibernate缓存机制
- (hdu step 7.1.2)You can Solve a Geometry Problem too(乞讨n条线段,相交两者之间的段数)
- vue-router2.0动态路由获取参数
- Rational Rose正逆向工程(类图转Java代码,Java代码转类图)
- 你应该学会的Python多版本管理工具Pyenv
- js调用app启动页
- 【pygame游戏编程】第二篇-----移动图像
- webvirtmgr-重命名kvm虚拟机的名称
- xml文档的读取
- Linux VMware安装CentOS
- [剑指Offer]50-第一个只出现一次的字符