单词环
原题链接
题目描述
我们有 \(n\) 个字符串，每个字符串都是由 \(a∼z\) 的小写英文字母组成的。
如果字符串 \(A\) 的结尾两个字符刚好与字符串 \(B\) 的开头两个字符相匹配，那么我们称 \(A\) 与 \(B\) 能够相连（注意：\(A\) 能与 \(B\) 相连不代表 \(B\) 能与 \(A\) 相连）。
我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。
如下例：
第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为 \(5+7+10=22\)（重复部分算两次），总共使用了 \(3\) 个串，所以平均长度是 \(\dfrac{22}{3}\approx 7.33\)。
思路
建图
如果直观的把每个单词看成一个节点，每个节点之间连一条边的话，在最坏的情况下有 \(10^5\) 个节点，那么会有 \(10^{10}\) 条边，我们是不能接受这样的数量级的。考虑到把单词看成一条边，前2个字母组成的单词和后2个字母组成的单词看成两个节点，那么节点数最多会有 \(26\times 26=676\) 个。
01分数规划
本题要求 \(\dfrac{\sum len}{count}\) 的最大值，设答案左端点为 \(l\)，右端点为 \(r\)，即中点为 \(mid\)，要满足 \(\dfrac{\sum len}{count}>mid\)，即 \(\sum len-count\times mid>0\)。
所以问题就转化为图中是否存在一个正环，权值为 \(len-mid\)。
优化
在用SPFA求正环的过程中，可以采取一种比较取巧的方法:
当求最长路时，经过的点大于某一个数时，我们就可以武断地认为当前图中存在一个正环。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87 | #include <bits/stdc++.h>
using namespace std;
const int N = 700, M = 100010;
int n;
int h[N], e[M], w[M], ne[M], idx;
double dist[N];
int cnt[N];
bool st[N];
int get(char a, char b) {
return (a - 'a') * 26 + (b - 'a');
}
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(cnt, 0, sizeof cnt);
memset(st, false, sizeof st);
queue<int> q;
for (int i = 0; i < 676; i++) {
q.push(i);
st[i] = true;
}
int count = 0;
while (q.size()) {
int u = q.front();
q.pop();
st[u] = false;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] < dist[u] + w[i] - mid) {
dist[j] = dist[u] + w[i] - mid;
cnt[j] = cnt[u] + 1;
if (++count > 10000) return true;
if (cnt[j] >= N) return true;
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
while (cin >> n, n) {
memset(h, -1, sizeof h);
idx = 0;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int len = s.size();
int left = get(s[0], s[1]);
int right = get(s[len - 2], s[len - 1]);
add(left, right, len);
}
if (!check(0)) {
cout << "No solution" << endl;
} else {
double l = 0, r = 1000;
while (r - l > 1e-4) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
cout << fixed << setprecision(2) << r << endl;
}
}
return 0;
}
|