【题解】JZOJ3852 单词接龙

题意

单词接龙，但是后两个字母匹配。求匹配环的单词平均长度的最大值。

正解

单词为有向边，边的长度为单词长度，前后两组字母为点，于是这个图只有 $26^2$ 个点。问题转化为求环的平均边长的最大值。

二分这个答案，所有边都减去这个值。若存在正环，则答案可以变大，否则变小。判环用 SPFA，最短路变成最长路就可以判正环了。答案的精度只有 $10^{-2}$，实数二分容易通过。

最大平均值就是分数规划裸题。——dzr

这个分数规划不懂什么意思。

实现

注意判环的时候是入队次数大于 $26^2$ 而不是大于 $n$。

#include 
using namespace std;
const int N = 1005;
const double eps = 1e-4;
int n, cnt = 0, fir[N], nxt[N * N], to[N * N], sum[N], vis[N], rt;
char s[N];
double val[N * N], dis[N];
void ade(int u, int v, double w) { cnt++, nxt[cnt] = fir[u], fir[u] = cnt, to[cnt] = v, val[cnt] = w; }
queue<int> q;
bool spfa(double x) {
	memset(sum, 0, sizeof(sum)), memset(dis, -0x3f, sizeof(dis)), dis[rt] = sum[rt] = 0, q.push(rt), vis[rt] = 1;
	while (!q.empty()) {
		int h = q.front();
		q.pop(), vis[h] = 0;
		for (int i = fir[h]; i; i = nxt[i])
			if (dis[to[i]] < dis[h] + val[i] - x) {
				dis[to[i]] = dis[h] + val[i] - x, sum[to[i]] = sum[h] + 1;
				if (sum[to[i]] > 27 * 27) return true;
				if (!vis[to[i]]) vis[to[i]] = 1, q.push(to[i]);
			}
	}
	return false;
}
int main() {
	scanf("%d", &n);
	for (int i = 1, len; i <= n; i++) {
		scanf("%s", s + 1), len = strlen(s + 1);
		if (len != 1) ade((s[1] - 'a' + 1) * 27 + s[2] - 'a' + 1, (s[len - 1] - 'a' + 1) * 27 + s[len] - 'a' + 1, len), rt = (s[1] - 'a' + 1) * 27 + s[2] - 'a' + 1;
	}
	double l = 2.0, r = 1000.0;
	int fl = 0;
	while (r - l > eps) {
		double mid = (l + r) / 2.0;
		if (spfa(mid)) l = mid, fl = 1;
		else r = mid;
	}
	if (fl) printf("%.2lf", l);
	else printf("No solution.");
	return 0;
}
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