SP2885 WORDRING - Word Rings

平均值，依然考虑分数规划。设当前二分平均值为 $x$ ，环中有 $k$ 个字符串，长度为 $w _ i$ ，则 $x$ 合法的条件为：
$$
\begin{aligned}
& \frac {\sum _ {i = 1} ^ k w _ i} k \ge x \\
\Longrightarrow & \sum _ {i = 1} ^ k w _ i \ge x k \\
\Longrightarrow & \sum _ {i = 1} ^ k w _ i \ge \sum _ {i = 1} ^ k x \\
\Longrightarrow & \sum _ {i = 1} ^ k w _ i - x \ge 0
\end{aligned}
$$
找正环即可。注意到 $n$ 的范围，如果暴力两两判断建边，时空复杂度是不可接受的。一个字符串的有效信息只有前两个字符和后两个字符，将这两组两个字符作为点，一个字符即开头两点到结尾两点的边。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const double eps = 1e-4;
const int N = 677, M = 1e5 + 10;
bool vis[N], need[N];
double d[N];
int n, cnt[N];
int idx = -1, hd[N], nxt[M], edg[M], wt[M];
bool check(double x)
{
    queue <int> q;
    for (int i = 1; i < N; i++)
        d[i] = cnt[i] = 0;
    for (int i = 0; i < N; i++)
        if (need[i])
        {
            q.push(i);
            vis[i] = true;
        }
    int times = 0;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for (int i = hd[t]; ~i; i = nxt[i])
            if (d[t] + wt[i] - x > d[edg[i]])
            {
                d[edg[i]] = d[t] + wt[i] - x;
                cnt[edg[i]] = cnt[t] + 1;
                if (++times > 1e4)
                    return true;
                if (cnt[edg[i]] >= n * 2)
                    return true;
                if (!vis[edg[i]])
                {
                    q.push(edg[i]);
                    vis[edg[i]] = true;
                }
            }
    }
    return false;
}
void add(int x, int y, int z)
{
    nxt[++idx] = hd[x];
    hd[x] = idx;
    edg[idx] = y;
    wt[idx] = z;
}
int num(char x, char y)
{
    int a = x - 'a',
        b = y - 'a';
    return a * 26 + b;
}
int main()
{
    int lth;
    string str;
    double l, r, mid;
    while (cin >> n, n)
    {
        for (int i = 0; i < N; i++)
            hd[i] = -1;
        idx = -1;
        for (int i = 0; i < n; i++)
        {
            cin >> str;
            lth = str.size();
            if (lth > 1)
            {
                int t = num(str[0], str[1]),
                    h = num(str[lth - 2], str[lth - 1]);
                need[t] = need[h] = true;
                add(t, h, lth);
            }
        }
        if (!check(0))
        {
            cout << "No solution." << endl;
            continue;
        }
        l = 0, r = N;
        while (r - l > eps)
        {
            mid = (l + r) / 2;
            if (check(mid))
                l = mid;
            else
                r = mid;
        }
        printf("%.2lf\n", r);
    }
    return 0;
}