10082. 「一本通 3.3 例 1」Word Rings
题意
每组数据读入一个n和n个字符串。定义前2个与末尾2个字母相同可以连接。问使这个环串的平均长度最大。求这个最大值。不存在输出No solution。
思路
平均值公式：
那么可以二分答案：
然后瞎搞spfa。
代码语言：javascript复制#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 '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("%.2lfn",ans);
else puts("No solution");
n=read();
}
return 0;
}
