解题思路
\(\qquad\)我们一开始可以得出一个建图的思路，对于每个字符串我们把它们当成图中的一个点，然后能“接龙”的字符串之间连一条边，在这张图上跑\(01\)分数规划。这样貌似是可以的，但是我们看一下这张图有多么庞大：它的点数\(N\)的上限可以达到\(10^5\)，而边数应该是\(A_{N}^{2}\)近似于\(N^2\)也就是差不多\(10^{10}\)，这显然是一个光建图就会超时的时间复杂度，我们不可以采用。
\(\qquad\)稍加思考我们可以得到另一个思路：将能接龙的字符串的首尾\(2\)位看做是点，连有向边，有向边的边权是这个字符串的长度。
\(\qquad\qquad\qquad\quad\Large\color{Red}{ --但是为什么可以这样做呢--}\)
\(\qquad\)我们经过观察，可以得到这样一个结论：
\(\qquad\)在本题中，只要两个字符串的首尾和长度相同，就可以看做是同一个字符串
上述结论的推导：
假设有两个字符串，\(\large s_{1}\)和\(\large s_{2}\)，我们的图中（第一个\(TLE\)礼包图）中存在这样的一个环：
\(\qquad \qquad\qquad\large c_1->c_2->c_3->c_4->s_1->c_5->c_6\)
当我们将\(\large s_2\)带进去的时候，由于\(\large s_2\)的首尾和\(\large s_1\)都是相同的，所以\(\ \large s_2\)必然可以和\(\ \large c_4\)以及\(\ \large c_5\)连接。然后由于点的数量不变，而边的权重又都相同，那自然平均值不变，所以这个环：
\(\qquad \qquad\qquad\large c_1->c_2->c_3->c_4->s_2->c_5->c_6\)
和上面的环是等价的。
01分数规划的解题思路
这题要求出一个环，使得这个环（点的个数是\(pcnt\)）的\(\LARGE \frac{\sum w_i}{pcnt}\)最大。
一样的用二分的思路，我们想要二分出这个最大值，假设当前二分的值是\(mid\)
当\(mid<ans\)的时候，也就是\(mid<\)\(\LARGE \frac{\sum w_i}{pcnt}\)的时候，\(check\)函数返回真值
将上式进行一点变形：
\(\qquad\qquad\qquad\qquad\qquad \LARGE mid\times pcnt < \sum w_i\)
\(\qquad\)
\(\qquad\qquad\qquad\qquad\qquad \LARGE mid\times pcnt - \sum w_i < 0\)
然后它就成了熟悉的负环题了，用\(SPFA\)判个环就好了
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 700;
int h[M], e[N], w[N], ne[N], idx;
double dist[M];
int st[M], ring, n;
string str;
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
void dfs(int cur, double x)
{
st[cur] = 1;
for (int i = h[cur]; ~i; i = ne[i])
{
int j = e[i]; double W = x - w[i];
if (dist[j] > dist[cur] + W)
{
dist[j] = dist[cur] + W;
if (st[j] == 1) {
ring = true ;
break ;
}
dfs(j, x);
if (ring) return ;
}
}
st[cur] = 2;
}
bool check(double x)
{
ring = 0;
memset(st, 0, sizeof st);
memset(dist, 0, sizeof dist);
for (int i = 1; i <= 676; i ++ )
{
if (st[i]) continue ;
if (ring) break ;
dfs(i, x);
}
return ring;
}
int main()
{
while (scanf("%d", &n), n)
{
idx = 0;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
{
cin >> str;
int len = str.size();
int a = (str[0] - 'a') * 26 + str[1] - 'a';
int b = (str[len - 2] - 'a') * 26 + str[len - 1] - 'a';
add(a + 1, b + 1, len);
}
if (!check(0)) puts("No solution");
else
{
double l = 0, r = 1e5;
while (r - l > 1e-4)
{
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.2lf\n", r);
}
}
return 0;
}