题目描述

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

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

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

如下例：

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

输入格式
本题有多组数据。

每组数据的第一行，一个整数 n，表示字符串数量；

接下来 n 行，每行一个长度小于等于 1000 的字符串。

读入以 n=0 结束。

输出格式
若不存在环串，输出”No solution”，否则输出最长的环串的平均长度。

只要答案与标准答案的差不超过 0.01，就视为答案正确。

数据范围
1≤n≤10^5

样例

输入样例：
3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0
输出样例：
21.66

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=700,M=100010;
int n;
int h[N],e[M],ne[M],w[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++){
        st[i]=true;
        q.push(i);
    }
    int count=0;
    while(q.size()){
        int x=q.front();
        q.pop();
        st[x]=false;
        for(int i=h[x];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]<dist[x]+w[i]-mid){//重新赋予边权，找正环，所以是找最长路径
            dist[j]=dist[x]+w[i]-mid;
            cnt[j]=cnt[x]+1;
            if(++count>2*n)return true;//经验，更新次数超过了2*n可能有环
            if(cnt[j]>=N)return true;
            if(!st[j]){
                st[j]=true;
                q.push(j);
            }   

            }

        }
    }
    return false;
}
int main(){
    string s;
    while(cin>>n){
        memset(h,-1,sizeof h);
        idx=0;
        for(int i=0;i<n;i++){
            cin>>s;
            int len=s.size();
            if(len>=2){
                int left=(s[0]-'a')*26+s[1]-'a';//用26进制存点
                int right=(s[len-2]-'a')*26+s[len-1]-'a';
                add(left,right,len);
            }
        }
        if(!check(0))puts("No solution");//如果01分数等于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;
}