题目大意

我们有 $n$ 个字符串，每个字符串都是由 $a∼z$ 的小写英文字母组成的。

如果字符串 $A$ 的结尾两个字符刚好与字符串 $B$ 的开头两个字符相匹配，那么我们称 $A$ 与 $B$ 能够相连（注意：$A$ 能与 $B$ 相连不代表 $B$ 能与 $A$ 相连）。

我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。

如下例：

ababc
bckjaca
caahoynaab

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

分析

1.建图:

一个比较直观的建图方式是将每个单词作为一个节点,如果这两个单词能够相连,则在这两个单词之间连接一条有向边,此时最多有$10^5$个点,$10^{10}$条边,不能接受.
考虑一个对偶的建图方式,将每一个单词看作一条边,其开头两个字符和结尾两个字符为它两边的点.
这样建图的话,节点数就缩小到了$676$个($26*26$),边数为$10^{5}$条.

2.$0/1$分数规划

我们所要求的答案为$\frac{\sum len}{s}$的最大值,其中$s$表示单词个数,$len$表示每个单词的长度.
可以发现所求问题具有单调性,可以使用二分来求解.
设左端点为$l$,右端点为$r$,中点为$mid$,则当$\frac{\sum len}{s} > mid$时, $\sum len-s \times mid>0$,则可以将图中的边权设成$len[i] - mid$($len[i]$表示当前单词的长度).
在此基础上,原问题可以转化为求当前图中有无正环.

3.优化

在用SPFA求正环的过程中,可以采取一种比较取巧的方法:当求最长路时,经过的点大于某一个数时,我们就可以武断地认为当前图中存在一个正环.

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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 q[N], cnt[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(st, 0, sizeof(st));
    memset(cnt, 0, sizeof(cnt));
    int hh = 0, tt = 0;
    for (int i = 0; i < 676; 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 != -1; 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 (++count > 10000) return true;
                 if (cnt[j] >= N) return true;
                 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)) {
        if (n == 0) break;
        memset(h, -1, sizeof(h));
        idx = 0;
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            int len = strlen(str);
            if (len >= 2) {
                int left = (str[0] - 'a') * 26 + str[1] - 'a',
                    right = (str[len - 2] - 'a') * 26 + str[len - 1] - 'a';
                add(left, right, len);
            }
        }
        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;
}