该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

【题意】
我们有 n 个字符串，每个字符串都是由 a 至 z 的小写英文字母组成的。如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符匹配，那么我们称 A 与 B 能够相连（注意：A 能与 B 相连不代表 B 能与 A 相连）。我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。如下例：
ababc
bckjaca
caahoynaab

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

【输入格式】
本题有多组数据。

每组数据的第一行，一个整数 n，表示字符串数量；
接下来 n 行，每行一个长度小于等于 1000 的字符串。

读入以 0 结束。

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

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

【样例输入】
3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0

【输出】
21.66

【数据范围与提示】
对于全部数据，$1\le n\le 10^5$。

Hint

这是无优化的spfa，1秒勉强过：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int N=700,M=1110000;
double eps=1e-3;
struct edge{int x,y,c,pre;}a[M];int alen,last[N];
void ins(int x,int y,int c){ alen++;a[alen]=edge{x,y,c,last[x]};last[x]=alen;}
int n,dd[N];double d[N];
bool v[N];
char s[1100];
bool check(double mid)
{
memset(d,0,sizeof(d));memset(v,False,sizeof(v));
memset(dd,0,sizeof(dd));
deque<int>q;for(int i=1;i<=676;i++)q.push_back(i),v[i]=1;
while(!q.empty())
{
int x=q.front();q.pop_front();v[x]=0;
for(int k=last[x];k;k=a[k].pre)
{
int y=a[k].y;
if(d[y]<d[x]+a[k].c-mid)
{
d[y]=d[x]+a[k].c-mid;
dd[y]=dd[x]+1;if(dd[y]>676) return True;
if(v[y]==0) q.push_back(y),v[y]=1;
}
}
}
return False;
}
int main()
{
freopen("i1.in","r",stdin);
int n;while(scanf("%d",&n),n){
alen=0;memset(last&#44;0&#44;sizeof(last));
for(int i=1;i&lt;=n;i++)
{
	scanf("%s"&#44;s);
	int len=strlen(s);
	if(len&gt;=2)
	{
    	int x=(s[0]-'a')*26+s[1]-'a'+1;
    	int y=(s[len-2]-'a')*26+s[len-1]-'a'+1;
		ins(x&#44;y&#44;len);
	}
}
double l=0&#44;r=1000&#44;mid&#44;ans=-1;
while(l&lt;r)
{
	mid=(l+r)/2;
	if(check(mid))l=mid+eps&#44;ans=mid;
	else          r=mid-eps;
}
if(ans!=-1) printf("%.3lf\n"&#44;ans);
else printf("No solution\n");

}
return 0;

}

</p>

这是DFS优化的spfa，60毫秒，感觉有段没有必要学。：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int N=27*27,M=1110000;
double eps=1e-4;
struct edge{int x,y,pre;double c;}a[M];int alen,last[N];
void ins(int x,int y,double c){ alen++;a[alen]=edge{x,y,last[x],c};last[x]=alen;}
int n,id[N],v[N];
double d[N],maxlen; 
char s[1100];
bool flag;//判断是否出现正环 
void spfa(int x,int h,double len)
{
	if(flag) return;
    for(int k=last[x];k;k=a[k].pre)
    {
    	int y=a[k].y;
    	if(d[y]<d[x]+a[k].c-len)
    	{
    		d[y]=d[x]+a[k].c-len;
    		if(d[y]>maxlen) {flag=True;return ;}
    		if(v[y]==0) v[y]=h,spfa(y,h,len);
    		if(flag)return ;
    		if(v[y]==h)
    		{
    			flag=True;
    			return ;
    		}
    	}
    }
    v[x]=0;
}
bool check(double len)
{
	flag=False;
	fill(d,d+n+1,0);fill(v,v+n+1,0);
	for(int i=1;i<=n;i++)
	{
		v[i]=i,spfa(i,i,len);
		if(flag) break;
	}
	return flag;
}
int main()
{
	//freopen("i2.in","r",stdin);
    int nn;while(scanf("%d",&nn),nn){
    	
	alen=0;memset(last,0,sizeof(last));
    memset(id,0,sizeof(id));
    maxlen=0;
    n=0;
    for(int i=1;i<=nn;i++)
    {
    	scanf("%s",s);
    	int len=double(strlen(s));if(maxlen<len)maxlen=len;
    	int x=(s[0]-'a')*26+s[1]-'a';
    	int y=(s[len-2]-'a')*26+s[len-1]-'a';
    	if(!id[x])id[x]=++n;
    	if(!id[y])id[y]=++n;
    	ins(id[x],id[y],double(len));
    }
    maxlen*=nn;
    double l=0,r=1000,mid,ans=-1;
    while(l<r)
    {
    	mid=(l+r)/2;
    	if(check(mid))l=mid+eps,ans=mid;
    	else          r=mid-eps;
    }
    if(ans!=-1) printf("%.3lf\n",ans);
    else printf("No solution\n");

	}
    return 0;
}