分析

• （1）首先我们需要考虑如何建图：一种直观的建图方式是顶点是各个字符串，如果字符串s2能接在s1的后面，那么连一条从s1指向s2的边。这样的话图中顶点的个数最多有$10^5$个，可能是完全图，因此边的数量在$10^{10}$量级，会超时，因此这样的建图方式不可取。

• 我们换一种建图的方式：顶点表示一个字符串的前两个字母或者后两个字母，边表示字符串的长度。相当于将上面一种建图方式中的顶点变成了边，边变成了顶点。这样的话，图中顶点的个数为676（$26\times 26$），边数最多$10^5$个。

• （2）另外我们还需要考虑一个问题，如何使得

$$ \frac{\sum w_i}{\sum s_i} \quad w_i表示环上字符串长度，s_i恒为1 $$

最大。我们可以使用和上一题一样的思路：01分数规划，使用二分解决。

• 针对本题，因为$1\le w[i] \le 1000$，所以答案所在的范围是：(0, 1000]，可以对该区间进行二分。

• 对于区间[l, r]以及mid=(l + r) / 2，如果有

$$ \frac{\sum w_i}{\sum 1} > mid $$

则说明答案在[mid, r]之间，否则答案在[l, mid]之间，接着二分即可。

• 对上面的不等式进行变形：

$$ \frac{\sum w_i}{\sum 1} > mid \\ \sum w_i - mid \times \sum 1 > 0 \\ \sum (w_i-mid \times 1) > 0 $$

• 根据上面的变形，每条边的权值变为$w_i-mid$，在变换边权之后，最终问题就转化成了：图中是否存在正环。

• 那么如何求解正环呢？可以将所有的边权取个反，问题就变成了是否存在负环；但是实际上我们不需要这样做，我们只需要求最长路径即可。

• （3）另外题目可能没有解，如何判断这种情况呢？对于改变后的边权$w_i-mid$，这个值越大，越有可能有正环，如果mid取0时都没有正环，则说明没有解。特判一下即可，我们可以使用AcWing 361. 观光奶牛的做法解决这个问题。

• （4）如果单纯使用AcWing 361. 观光奶牛方法解决这个问题，会超时（TLE），因此需要使用上面原理中提到的技巧：当所有的点入队的次数超过2n（或者3n）时，我们就认为图中有很大可能是存在负环的。但是注意：本题的点数太少，不到700，但是边数非常多，最多有10000条，所以经验值不适用了，需要取一个更大的值。

• 另外对于求负环的问题，如果超时的话，我们还可以尝试将队列改为栈，有可能更快找到这个环，这样一般都是能解决TLE问题的。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 700, M = 100010;

int n;  // 图中边数，有多少字符串就有多少条有向边
int h[N], e[M], w[M], ne[M], idx;
double dist[N];
int cnt[N];  // cnt[i]表示到达i的最长路径经过的边数
int q[N];  // 循环队列
bool st[N];  // 代表点是否在队列中

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool check(double mid) {

    memset(cnt, 0, sizeof cnt);

    int hh = 0, tt = 0;
    for (int i = 0; i < 26 * 26; i++) {
        q[tt++] = i;
        st[i] = true;
    }

    int count = 0;
    while (hh != tt) {

        int t = q[hh++];
        if (hh == N) hh = 0;

        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i] - mid) {
                dist[j] = dist[t] + w[i] - mid;
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= N) return true;  // n是边数，N才是点数

                if (++count > N * 10) return true;  // 经验上的trick

                if (!st[j]) {
                    q[tt++] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main() {

    char str[1010];
    while (scanf("%d", &n), n) {

        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            int c = strlen(str);
            if (c >= 2) {
                int a = (str[0] - 'a') * 26 + str[1] - 'a';
                int b = (str[c - 2] - 'a') * 26 + str[c - 1] - 'a';
                add(a, b, c);
            }
        }

        if (!check(0)) puts("No solution");
        else {
            double l = 0, r = 1000;
            while (r - l > 1e-4) {
                double mid = (l + r) / 2;
                if (check(mid)) l = mid;
                else r = mid;
            }

            printf("%lf\n", r);
        }
    }

    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 700, M = 100010;

int n;  // 图中边数，有多少字符串就有多少条有向边
int h[N], e[M], w[M], ne[M], idx;
double dist[N];
int cnt[N];  // cnt[i]表示到达i的最长路径经过的边数
int stk[N];  // 栈
bool st[N];  // 代表点是否在栈中

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool check(double mid) {

    memset(cnt, 0, sizeof cnt);

    int tt = 0;
    for (int i = 0; i < 26 * 26; i++) {
        stk[++tt] = i;
        st[i] = true;
    }

    while (tt > 0) {  // 此时tt指向栈顶元素

        int t = stk[tt--];

        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i] - mid) {
                dist[j] = dist[t] + w[i] - mid;
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= N) return true;  // n是边数，N才是点数

                if (!st[j]) {
                    stk[++tt] = j;
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main() {

    char str[1010];
    while (scanf("%d", &n), n) {

        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            int c = strlen(str);
            if (c >= 2) {
                int a = (str[0] - 'a') * 26 + str[1] - 'a';
                int b = (str[c - 2] - 'a') * 26 + str[c - 1] - 'a';
                add(a, b, c);
            }
        }

        if (!check(0)) puts("No solution");
        else {
            double l = 0, r = 1000;
            while (r - l > 1e-4) {
                double mid = (l + r) / 2;
                if (check(mid)) l = mid;
                else r = mid;
            }

            printf("%lf\n", r);
        }
    }

    return 0;
}