1165. 单词环

解题报告：这题可以用spfa判断正环的做法+二分来做，我们二分他的环的平均长度，看看能不能凑成环，如果暴力去把每个字符串变成一个点，总共会有1e5的点，可以优化一下，把整个字符串变成一条边，把前两个和后两个的单词字母映射成一个点，总共26*26个点，如果朴素去做会tle，那么要加个玄学优化，如果更新次数太多的话（十几倍左右）就暂且认为他是一个环，然后stl的queue太慢了，要用数组来模拟队列。

#include<bits/stdc++.h>
using namespace std;
const   int N=100010,M=700;
int h[M],e[N],ne[N],idx;
double w[N];
bool st[M];
int cnt[M];
double dist[M];
int q[N];
int n;
void add(int a,int b,int c)
{
   
    e[idx]=b,ne[idx]=h[a],w[idx]=c,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==M)   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(!st[j])
            {
   
                st[j] = true;
                q[tt++]=j;
                if(tt==M)   tt=0;
            }
            if(cnt[j]>=M)   return true;
            if(++count>=10000)  return true; // 经验上的trick
        }
        
    }
    }
    return false;
}
int main()
{
   
    while(cin>>n,n)
   {
   
       idx=0;
      memset(h,-1,sizeof h);
    for(int i=0;i<n;i++)
    {
   
        string s;
        cin >> s;
        if(s.size()>=2)
       {
    int id = (s[0]-'a')*26 + (s[1]-'a');
        int id2=(s[s.size()-2]-'a')*26 + (s[s.size()-1]-'a');
        add(id,id2,s.size());
        }
    }
        double l=0,r=1e3;
        if(!check(0))
        cout<<"No solution"<<endl;
        else
       {
    
           while(r-l>1e-4)
        {
   
            double mid=(l+r)/2;
            if(check(mid))
            l=mid;
            else
            r=mid;
        }
        printf("%.2lf\n",l);
       }
        
   }
   return 0;
}