1504：【例 1】Word Rings

【题目描述】

原题来自：Centrual Europe 2005

我们有 n 个字符串，每个字符串都是由 a 至 z 的小写英文字母组成的。如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符匹配，那么我们称 A 与 B 能够相连（注意：A 能与 B 相连不代表 B 能与 A 相连）。我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。如下例：

ababc
bckjaca
caahoynaab

 

第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为 5+7+10=22（重复部分算两次），总共使用了 3 个串，所以平均长度是 <span id=”MathJax-Span-2″ class=”mrow”><span id=”MathJax-Span-3″ class=”mfrac”><span id=”MathJax-Span-4″ class=”mn”>22<span id=”MathJax-Span-5″ class=”mn”>3<span id=”MathJax-Span-6″ class=”mo”>≈<span id=”MathJax-Span-7″ class=”mn”>7.33223≈7.33。

【输入】

本题有多组数据。

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

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

读入以 0 结束。

【输出】

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

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

【输入样例】

3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0

【输出样例】

21.66

【提示】

数据范围：

对于全部数据，1≤n≤10⁵​​ 。

【代码】

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<stack>

#include<cstdio>

#include<queue>

#include<map>

#include<vector>

#include<set>

using namespace std;

const int maxn=1e5+10;

const int INF=0x3fffffff;

const double eps=1e-4;

typedef long long LL;

char aa[1010];

int head[maxn],vis[maxn];

double dis[maxn];

int n,cnt;

struct node

{

int to,next,dis;

}

ed[maxn*10];

void add(int a,int b,int c)

{

ed[++cnt].to=b;

ed[cnt].dis=c;

ed[cnt].next=head[a];

head[a]=cnt;

}

int js(char a,char b)

{

return (a-‘a’)*26+(b-‘a’)+1;

}

bool spfa(int x,double mid)

{

vis[x]=1;

for(int i=head[x];i;i=ed[i].next)

{

int t=ed[i].to;

if(dis[x]+ed[i].dis-mid>dis[t])

{

dis[t]=dis[x]+ed[i].dis-mid;

 if(vis[t]||spfa(t,mid))

{

vis[x]=0;

return 1;

}

}

}

vis[x]=0;

return 0;

}

bool judge(double mid){

memset(dis,0,sizeof(dis));

for(int i=1;i<=26*26;i++)

{

if(spfa(i,mid))

return 1;

}

return 0;

}

int main()

{

while(scanf(“%d”,&n)&&n)

{

memset(vis,0,sizeof(vis));

memset(head,0,sizeof(head));

for(int i=0;i<n;i++)
{

scanf(“%s”,aa);

int len=strlen(aa);

add(js(aa[0],aa[1]),js(aa[len-2],aa[len-1]),len);

}

double mid,left=0,right=1000;

while(right-left>=eps)

{

mid=(left+right)/2;

if(judge(mid)) 

{

left=mid;

}

else right=mid;

}

if(left==0)

printf(“No solution/n”);

 else printf(“%.2lf/n”,left);

}

return 0;

}