#10082. 「一本通 3.3 例 1」Word Rings - 题目 - LibreOJ (loj.ac)
题目描述
原题来自：Centrual Europe 2005
我们有 个字符串，每个字符串都是由 a 至 z 的小写英文字母组成的。如果字符串 的结尾两个字符刚好与字符串 的开头两个字符匹配，那么我们称 与 能够相连（注意： 能与 相连不代表 能与 相连）。我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。如下例：
ababc
bckjaca
caahoynaab
第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为 （重复部分算两次），总共使用了 个串，所以平均长度是 。
输入格式
本题有多组数据。
每组数据的第一行，一个整数 ，表示字符串数量；
接下来 行，每行一个长度小于等于 的字符串。
读入以 结束。
输出格式
若不存在环串，输出 No solution，否则输出最长的环串的平均长度。
只要答案与标准答案的差不超过 ，就视为答案正确。
样例
输入
3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0输出
21.66数据范围
对于全部数据, 。
思路
给几个字符串, 其中若A串末尾两个字符和B串头两个字符相同则可以相连, 若存在三个串首尾相连就可以形成一个环, 让我们求出可以拼接出来的环长度平均值的最大值, 重复部分会算两次, 即A串和B串连接后得到的长度是A长度+B长度。
既然是分数形式, 试着往01分数规划方面思考, 这里的最大值也有上下界：, 最小不小于0, 每个串都长度最大是取最大值。 定义区间中点为 , 可以通过二分条件 来求解, 转化为： 而 是拼接的字符串个数, 这里则都是1, 可以省去：
那么现在就是判断是否能构成一个正环。
求环的话试着建图, 若把一个字符串当做一个节点, 点权值为当前字符串长度, 边权值为1。最大共有 个点, 若所有字符串都一样, 那就是全连接图 条边, 显然是无法通过SPFA解决的东西。
换一种建图方式, 根据题目的条件, 一个字符串除了前面两个和后面两个字符, 中间字符是什么我们没必要关心和维护, 它们的贡献只有长度。那么对于一个串, 把前两个字符和后两个字符视为两个点, 该串的长度视为这两个点之间的边权。这样即保留了原本信息, 还可以满足题目首尾相接的条件。总点数也就 个, 全连接图的话边数为 , 总时间复杂度最坏为 , 不过这种卡边界的时间可以通过一些优化来解决。
比如提前终止搜索和把队列改成栈两种方法都可以过。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 700, M = 1e6;
int n;
int h[N], e[M], ne[M], w[M], idx;
double dist[N];
bool st[N];
int q[N], cnt[N];
void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
bool check(double mid)
{
memset(st, 0, sizeof st);
memset(cnt, 0, sizeof cnt);
int hh = 0, tt = 0;
for (int i = 0; i < 676; i++)
q[tt++] = i, st[i] = true;
while (hh != tt)
{
int t = q[--tt];
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] < dist[t] + w[i] - mid)
{
dist[j] = dist[t] + w[i] - mid;
cnt[j] = cnt[t] + 1;
if (cnt[j] >= N)
return true;
if (!st[j])
q[tt++] = j, st[j] = true;
}
}
}
return false;
}
int main()
{
while (cin >> n, n)
{
memset(h, -1, sizeof h);
idx = 0;
char s[1010];
for (int i = 0; i < n; i++)
{
cin >> s;
int m = strlen(s) - 1;
if (m + 1 < 2)
continue;
int a = (s[0] - 'a') * 26 + (s[1] - 'a'), b = (s[m - 1] - 'a') * 26 + (s[m] - 'a');
add(a, b, m + 1);
}
if (!check(0))
{
cout << "No solution\n";
continue;
}
double l = 0, r = 1000;
while (r - l > 1e-4)
{
double mid = (l + r) / 2.0;
if (check(mid))
l = mid;
else
r = mid;
}
printf("%.2lf\n", r);
}
return 0;
}