本题的关键在于：
1. 建图
2. 01分数规划
3. 本题的数据过大，如果直接spfa判断会TLE，因此我们使用经验优化，就是如果所有的点入队的次数过多，比如大于100000，那么我们直接认为它是存在正环的。（免去TLE，但是这个不一定对）

• 建图

做一个对偶

主要是除了两端的两个字母有用以外，字符串中间的其他所有的字符都没有用，因此我们可以直接这样建图：直接hash两端的两个字母作为结点，边的权值为该字符串的个数。这样建的图结点和边的个数为1e7，没有超限。

如果我们直接像下面这样暴力建图，数据会达到1e10，不可取。

- 题目要求先判断是否有解：

如果m = 0的时候无解，那么m>0时更无解

• 01规划：

我们要求的是平均长度，也就是每一条字符串的长度之和除以总的字符串个数，换成数学公式即为下式（个数对于每一个字符串来说都是1）：
$$\frac{\sum w_i}{\sum 1}$$
要求这个值最大，满足单调性，很明显是一个01分数规划问题，自然使用二分答案。我们设答案为mid
那么如果当前答案不够需要更大，上式即为$$\frac{\sum w_i}{\sum 1}>mid$$
化简以后：$$\sum w_i>mid * \sum 1$$
$$\sum w_i>\sum mid $$
$$\sum w_i - \sum mid > 0$$

那么也就是说对于每一个边，给它赋权值$w_i - mid$，如果存在正环，也就意味着有一个环的权值和大于0，也就是$\sum w_i - \sum mid > 0$，就意味着mid需要更大。

这里可以直接用权值建图，然后直接跑spfa，把不同的mid放到更新最短路时减去，因为每次只是-mid，跟其他的没有关系，就不用像上一道题那样每次重新建图了。

eps=1e-4，应该是double类型!

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>


using namespace std;

const int N = 1000, M = 500007, INF = 0x3f3f3f3f;
const double eps = 1e-4;

int ver[M],nex[M],edge[M],head[N],tot = 1;
int n;//这里的n是字符的个数
int m;
int q[N],cnt[N],vis[N];
double dist[N];

void add(int x,int y,int z){
    ver[++tot] = y;
    edge[tot] = z;
    nex[tot]  =head[x];
    head[x] = tot;
}

bool check(double mid){
    memset(cnt,0,sizeof cnt);
    memset(vis,0,sizeof vis);

    int hh = 0,tt = 0;

    for(int i = 0;i < 676;++i){
        q[tt ++ ] = i;
        vis[i] = true;
    }
    int counts = 0;//经验优化
    while(hh != tt){
        int x = q[hh ++ ];
        if(hh == N)hh = 0;
        vis[x] = false;

        for(int i = head[x];~i;i = nex[i]){
            int y = ver[i],z = edge[i];
            if(dist[y] < dist[x] + z - mid){
                dist[y] = dist[x] + z - mid;
                cnt[y] = cnt[x] + 1;
                counts ++ ;
                if(counts > 10000)return true;
                if(cnt[y] >= N)return true;
                if(!vis[y]){
                    vis[y] = true;
                    q[tt ++ ] = y;
                    if(tt == N)tt = 0;
                }
            }
        }
    }
    return false;
}

int main(){
    while(scanf("%d",&n) && n){
        memset(head,-1,sizeof head);
        tot = 1;
        for(int i = 1;i <= n;++i){
            char s[1010];
            scanf("%s",s);
            int len = strlen(s);

            if(len < 2)continue;
            int a = (s[0] - 'a' )* 26 + s[1] - 'a';
            int b = (s[len - 2] - 'a') * 26 + s[len - 1] - 'a';
            add(a,b,len);
        }
        if(!check(0))puts("No solution");
        else {
            double l = 0,r = 1000;
            while(r - l > eps){
                double mid = (l + r) / 2;
                if(check(mid))l = mid;
                else r = mid;
            }
            printf("%lf\n",r);
        }
    }
    return 0;
}