单词环

题目描述

我们有 $n$ 个字符串，每个字符串都是由 $a-z$ 的小写英文字母组成的。 如果字符串 $A$ 的结尾两个字符刚好与字符串 $B$ 的开头两个字符相匹配，那么我们称 $A$ 与 $B$ 能够相连（注意：$A$ 能与 $B$ 相连不代表 $B$ 能与 $A$ 相连）。 我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。 如下例： ababc bckjaca caahoynaab 第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为 $5+7+10=22$（重复部分算两次），总共使用了 $3$ 个串，所以平均长度是 $22 \div 3≈7.33$。

输入输出说明

样例输入

本题有多组数据。 每组数据的第一行，一个整数 $n$，表示字符串数量； 接下来 $n$ 行，每行一个长度小于等于 $1000$ 的字符串。 读入以 $n=0$ 结束。

样例输出

若不存在环串，输出 No solution ，否则输出最长的环串的平均长度。 只要答案与标准答案的差不超过 $0.01$，就视为答案正确。

题目样例

样例输入

3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0

样例输出

21.66

数据范围

对于 $100\%$ 数据满足,$1≤n≤10^5$

---

这是我的代码：

/**
* By @xusiyuan 
* In YUANSHIREN
* C++
**/

# include <bits/stdc++.h>
# define N 1005
# define M 100005

using namespace std;

int head[N], ver[M], Next[M], edge[M], n, m, tot;
void ADD (int x, int y, int z) {
	ver[++tot] = y;
	edge[tot] = z;
	Next[tot] = head[x];
	head[x] = tot;
}

double dist[N];
bool vis[N];
int cnt[N];
char S[N];

bool check(double mid) {
	memset(vis, 0, sizeof(vis));
	memset(dist, 0, sizeof(dist));
	memset(cnt, 0, sizeof(cnt));
	queue <int> Q;
	for (int i = 0; i <= n; i++) {
		Q.push(i);
		vis[i] = 1;
	}
	while (Q.size()) {
		int x = Q.front();
		Q.pop();
		vis[x] = 0;
		for (int i = head[x]; ~i; i = Next[i]) {
			int y = ver[i];
			if (dist[y] < dist[x] + edge[i] - mid) {
				dist[y] = dist[x] + edge[i] - mid;
				cnt[y] = cnt[x] + 1;
				if (cnt[y] >= n) return 1;
				if (!vis[y]) {
					Q.push(y);
					vis[y] = 1;
				}
			}
		}
	}
	return 0;
}

int main () {

	while (~scanf("%d", &m) && m != 0) {
		memset(head, -1, sizeof(head));
		tot = -1;
		n = 676;
		for (int i = 1; i <= m; i++) {
			scanf("%s", &S[1]);
			int len = strlen(S + 1);
			if (len >= 2) {
				int x = (S[1] - 'a') * 26 + (S[2] - 'a');
				int y = (S[len - 1] - 'a') * 26 + S[len];
				ADD(x, y, len);
			}
		}
		if (check(0) == 0) printf("No solution\n");
		else {
			double L = 1, R = 1000;
			while (R - L > 1e-7) {
				double mid = (L + R) / 2.0;
				if (check(mid)) L = mid;
				else R = mid;
			}
			printf("%.2lf", R);
		}
	}

	return 0;
}

全 WA 求条。