$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. 01分数规划问题，可以用二分解决，可参考观光奶牛
2. 从头的两个字母连向尾的两个字母，这样共有 26 * 26 = 676 个点
3. 每次二分答案，把边权看成 w[i] - mid，这样就只需要判定是否存在正环即可
4. 玄学经验值，一般循环次数大于点数的两倍就存在环

可参考： 观光奶牛

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 676, 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(cnt,0,sizeof cnt);
    memset(st,0,sizeof st);

    //把676个点都放进去
    queue<int> q;
    for(int i=0;i<676;i++)
    {
        q.push(i);
        st[i]=true;
    }

    int count=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        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(++count>=10000||cnt[j]>=N) return true;

                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }

    return false;
}

int main()
{
    char str[1010];
    while(cin>>n,n)
    {
        memset(h,-1,sizeof h);
        idx=0;

        //共 26 * 26 = 676 个点
        for(int i=0;i<n;i++)
        {
            cin>>str;
            int len=strlen(str);
            if(len>=2)
            {
                int a=(str[0]-'a')*26+str[1]-'a';
                int b=(str[len-2]-'a')*26+str[len-1]-'a';
                add(a,b,len);
            }
        }

        //连0都不可以的话，当边权更大时就更不可能了
        if(!check(0)) cout<<"No solution"<<endl;
        else 
        {
            //二分答案
            double l=0,r=1000;
            while(r-l>1e-4)
            {
                double mid=(l+r)/2;
                if(check(mid)) l=mid;
                else r=mid;
            }

            cout<<l<<endl;
        }
    }

    return 0;
}