10082. 「一本通 3.3 例 1」Word Rings

(Updated: )
oi
, ,

题意

每组数据读入一个n和n个字符串。定义前2个与末尾2个字母相同可以连接。问使这个环串的平均长度最大。求这个最大值。不存在输出No solution。

思路

平均值公式：
$$Average=(E_1+E_2+…..+E_n)/n$$ $$Average*n=(E_1+E_2+…+E_n)$$ $$(E_1-Average)+(E_2-Average)+…+(E_n-Average)=0$$ 那么可以二分答案：
$$(E_1-Ans)+(E_2-Ans)+…+(E_n-Ans)\geq0$$
然后瞎搞spfa。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#define E 200010
#define eps 1e-3
using namespace std;
inline int read(){
    int res=0,f=1;char ch=getchar();
    while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}
//queue<int> q;
//set<int> s;
//priority_queue<int> q1;
//priority_queue<int,vector<int>,greater<int> > q2;
//list<int> l;
//stack<int> s;
int n;
string str[100010];
int fir[E],nxt[E],son[E],tot,cnt,Max;
double w[E],dis[E],flag;
int vis[E];
int f[6666];
void add(int x,int y,double z){++tot;son[tot]=y;nxt[tot]=fir[x];fir[x]=tot;w[tot]=z;}
void spfa(int s,int v,double mid){
    if(flag==1) return ;
    vis[s]=v;
    for(int i=fir[s];i;i=nxt[i]){
        int to=son[i];
        if(dis[s]+w[i]>dis[to]+mid){
            dis[to]=dis[s]+w[i]-mid;
            if(dis[to]>Max){
                flag=1;
                return ;
            }
            if(!vis[to]) spfa(to,v,mid);
            if(flag) return ;
            else if(vis[to]==v){
                flag=1;
                return ;
            }
        }
    }
    vis[s]=0;
}
bool check(double mid){
    flag=0;
    for(int i=0;i<=cnt;i++) dis[i]=0.0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=cnt;i++){
        spfa(i,i,mid);
        if(flag==1) break;
    }
    return flag;
}
int main(){
//    freopen("code.in","r",stdin);freopen("code.out","w",stdout);
    n=read();
    while(n!=0){
        for(int i=1;i<=n;i++) cin>>str[i];
        memset(fir,0,sizeof(fir));
        memset(f,0,sizeof(f));
        tot=0;cnt=0;Max=0;
        for(int i=1;i<=n;i++){
            int len=str[i].length();
            Max=max(Max,len);
            int a=(str[i][0]-'a')*26+str[i][1]-'a';
            int b=(str[i][len-2]-'a')*26+str[i][len-1]-'a';
            if(!f[a]) f[a]=++cnt;
            int A=f[a];
            if(!f[b]) f[b]=++cnt;
            int B=f[b];
            add(A,B,(double)len);
        }
        Max*=n;
        double l=0,r=1000,ans=-1,mid;
        while(l+eps<r){
            mid=(l+r)/2;
            if(check(mid)) l=mid,ans=mid;
            else r=mid;
        }
        if(ans!=-1) printf("%.2lf\n",ans);
        else puts("No solution");
        n=read();
    }
    return 0;
}