Description

\\n【题意】
\\r\\n我们有 n 个字符串，每个字符串都是由 a 至 z 的小写英文字母组成的。如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符匹配，那么我们称 A 与 B 能够相连（注意：A 能与 B 相连不代表 B 能与 A 相连）。我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。如下例：
\\r\\nababc
\\r\\nbckjaca
\\r\\ncaahoynaab
\\r\\n
\\r\\n第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为 5+7+10=22（重复部分算两次），总共使用了 3 个串，所以平均长度是
\\r\\n
\\r\\n$\\\\frac{22}{3}\\\\approx 7.33$。
\\r\\n
\\r\\n【输入格式】
\\r\\n本题有多组数据。
\\r\\n
\\r\\n每组数据的第一行，一个整数 n，表示字符串数量；
\\r\\n接下来 n 行，每行一个长度小于等于 1000 的字符串。
\\r\\n
\\r\\n读入以 0 结束。
\\r\\n
\\r\\n【输出格式】
\\r\\n若不存在环串，输出 No solution，否则输出最长的环串的平均长度。
\\r\\n
\\r\\n只要答案与标准答案的差不超过 0.01，就视为答案正确。
\\r\\n
\\r\\n【样例输入】
\\r\\n3
\\r\\nintercommunicational
\\r\\nalkylbenzenesulfonate
\\r\\ntetraiodophenolphthalein
\\r\\n0
\\r\\n
\\r\\n【输出】
\\r\\n21.66
\\r\\n
\\r\\n【数据范围与提示】
\\r\\n对于全部数据，$1\\\\le n\\\\le 10^5$。
\\n

统计

递交统计

*【最短路】Word Rings[Centrual Europe 2005]

信息

状态

开发

支持

关于

还没有账户？

登录