关键点

1. 建图
   • 若按一个字符串一个点，那么有$ 10^5 * 10 ^5 $个点
   • 把一个字符串前两个字母 和 后两个字母看成点，那么有$ 26 * 26 $ 个点，$ 10 ^ 5 $ 条边（可以接受）
2. 01分数规划
   • 求 wi / si 最大，结合二分 使得 $wi / si > mid(si = 1)$, 移项得$ wi - mid * 1 > 0 $<–> 图中存在正环
3. 优化
   • 当SPFA迭代的总边数大于 边数的2倍，可认为存在环（经验上的trick）

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

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];
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);

    queue<int> q;
    for(int i=0;i<676;i++)
    {
        q.push(i);
        st[i] = 1;
    }

    int count = 0;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = 0;

        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( ++ count > 2 * n) return true; // 经验上的trick
                if(!st[j])
                {
                    q.push(j);
                    st[j] = 1;
                }
            }
        }
    }

    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 len = strlen(str);
            if(len >= 2)
            {
                int left = (str[0] - 'a') * 26 + str[1] - 'a'; // 转换为26进制的数
                int right = (str[len-2] - 'a') * 26 + str[len-1] - 'a';
                add(left,right,len);
            }
        }

        if(!check(0)) puts("No solution"); // 根据公式：wi - m*1 > 0,如果m =0都不存在正环，那么题目无解
        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;
}