链接：

loj：https://loj.ac/problem/10082

luogu：https://www.luogu.com.cn/problem/SP2885

SPOJ：https://www.spoj.com/problems/WORDRING/

对于每个字符串的首尾两个长度为\(2\)的子串，哈希之后连一条权为当前字符串的长度的有向边

然后题目只需要找到边权平均值最大的正环

设正环由\(k\)条边组成，分别标号为\(1,2,…,k\)，第\(i\)条边的长度为\(d_i\)

则平均值\(a=\dfrac{ \sum \limits^{k}_{i=1} d_i } {k}\)

然后\(\sum\limits^{k}_{i=1} (d_i - a) = 0\)

做上式大于\(0\)，则说明有更优解

于是考虑二分答案即可做出

代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(register int i=a;i<=b;++i)
inline int read()
{
    bool f=0;int x=0;char ch;
    do{ch=getchar();f|=(ch=='-');}while(!isdigit(ch));
    do{x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}while(isdigit(ch));
    return f?-x:x;
}
inline void write(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writesp(int x)
{
	write(x);putchar(' ');
}
inline void writeln(int x)
{
	write(x);puts("");
}
const int maxn=1e6+5; 
int head[maxn],nxt[maxn],w[maxn],to[maxn],vis[maxn],tot;
double dis[maxn];
void insert(int u,int v,int val)
{
    nxt[++tot]=head[u];
    head[u]=tot;
    w[tot]=val;
    to[tot]=v;
}
int spfa(double t,int u)
{
	vis[u]=1;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i],val=w[i];
		if(dis[v]<dis[u]+val-t)
		{
			dis[v]=dis[u]+val-t;
			if(vis[v]||spfa(t,v))
				return 1;
		}
	}
	vis[u]=0;
	return 0;
}
int check(double mi)
{
	memset(dis,0,sizeof(dis));
	memset(vis,0,sizeof(vis));
	rep(i,1,1e5)if(spfa(mi,i))return 1;
	return 0;
}
int main()
{
	while(1)
	{
		int n=read(),sum=0;tot=0;
		memset(to,0,sizeof(to));memset(w,0,sizeof(w));memset(nxt,0,sizeof(nxt));memset(head,0,sizeof(head));
		if(!n)break;
		rep(i,1,n)
		{
			string s;cin>>s;
			int len=s.size(),a=(s[0]-96)*100+(s[1]-96),b=(s[len-2]-96)*100+(s[len-1]-96);
			insert(a,b,len);
			sum+=len;
		}
		double l=0,r=sum,mid;
		while(l+1e-2<r)
		{
			mid=(l+r)/2;
			if(check(mid)) l=mid;
			else r=mid;
		}
		if(l==0)
			puts("No solution");
		else
			printf("%.2lf\n",l);
	}
	return 0;
}