单词环（图论、spfa找负环）

我们有 n 个字符串，每个字符串都是由 a∼z 的小写英文字母组成的。

如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符相匹配，那么我们称 A 与 B 能够相连（注意：A 能与 B 相连不代表 B 能与 A 相连）。

我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。

如下例：

ababc
bckjaca
caahoynaab
第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为 5+7+10=22（重复部分算两次），总共使用了 3 个串，所以平均长度是 22/3≈7.33。

输入格式

本题有多组数据。

每组数据的第一行，一个整数 n，表示字符串数量；

接下来 n 行，每行一个长度小于等于 1000 的字符串。

读入以 n=0 结束。

输出格式

若不存在环串，输出”No solution”，否则输出最长的环串的平均长度。

只要答案与标准答案的差不超过 0.01，就视为答案正确。

数据范围

1≤n≤10^5

输入样例：

3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
3
ababc
bckjaca
caahoynaab
2
abcd
xyz
1
aba
1
aa
1
aaa
0

输出样例：

21.66
7.33
No solution
No solution
2.00
3.00

思路：将每一个字符串当成一条边，前两个字符是起点后两个是终点，建图

#include<bits/stdc++.h>
using namespace std; using ll = long long;

const int N = 800, mod = 1e9 + 7, INF = 0x3f3f3f3f;

int n, m;

unordered_map<string, double> cnt, dist;

using psi = pair<string, int>;

unordered_map < string, vector < psi >> g;

void init() {
	g.erase(g.begin(), g.end());
	string ss;
	for (int i = 0; i < n; i++) {
		cin >> ss;
		g[ss.substr(0, 2)].emplace_back(ss.substr(ss.size() - 2, 2), ss.size());
	}
	return;
}

queue<string> qu;

unordered_map<string, bool> st;

bool spfa(double mid) {
	for (auto& [x, d] : g) {
		dist[x] = 0, st[x] = true, cnt[x] = 0, qu.emplace(x);
	}
	ll count = 0;
	while (qu.size()) {
		string x = qu.front();
		qu.pop();
		st[x] = false;
		for (auto& [nx, len] : g[x]) {
			double td = len - mid;
			if (dist[nx] < dist[x] + td) {
				dist[nx] = dist[x] + td;
				cnt[nx] = cnt[x] + 1;
				if (++count > 10ll * n)  // 经验上的trik
					return true;
				if (cnt[nx] >= n * 2ll) // n是边的数量，所以点的数量肯定要大于2 * n
					return true;
				if (st[nx]) continue;
				st[nx] = true;
				qu.emplace(nx);
			}
		}
	}
	return false;
}

void solve() {
	double l = 0, r = 100000;
	if (!spfa(l)) {
		cout << "No solution";
		return;
	}
	while (r - l > 1e-4) {
		double mid = (l + r) / 2;
		if (spfa(mid))
			l = mid;
		else
			r = mid;
	}
	cout << l;

	return;
}

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout << setprecision(10) << fixed;
	int TT = 1;
	//cin >> TT;
	for (int ii = 1; cin >> n, n; init(), solve(), ii++, cout << "\n") {}
	return 0;
}