1 / 6
文档名称:

最小生成树算法.docx

格式:docx   大小:24KB   页数:6页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

最小生成树算法.docx

上传人:文库旗舰店 2022/8/8 文件大小:24 KB

下载得到文件列表

最小生成树算法.docx

文档介绍

文档介绍:1789Truck History
Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 12194
Accepted: 4603
Description
se, your program should output the text "The highest possible quality is 1/Q.", where 1/Q is the quality of the best derivation plan.
Sample Input
4
aaaaaaa
baaaaaa
abaaaaa
aabaaaa
0
Sample Output
The highest possible quality is 1/3.
Source
CTU Open 2003
2485:Highways
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 15706
Accepted: 7323
Description
The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They're planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system.
Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.
The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.
Input
The first line of input is an integer T, which tells how many test