Word Rings
我们有$n$个字符串，每个字符串都是由$a$至$z$的小写英文字母组成的。如果字符串$A$的结尾两个字符刚好与字符串$B$的开头两个字符匹配，那么我们称$A$与$B$能够相连（注意:$A$能与$B$相连不代表$B$能与$A$相连）。
我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），使这个环串的平均长度最大。如下例：
ababc
bckjaca
caahoynaab
第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为$5+7+10=22$（重复部分算两次），总共使用了$3$个串，所以平均长度是$frac{22}{3} approx 7.33$。
解析
建图：把单词看成边，把首尾字母组合看成点。例如：对于单词$ababc$就是点"$ab$"向点"$bc$"连一条长度为$5$的边。
二分答案：二分平均长度$ave$。
SPFA：将图中每条边的权值减去$ave$，题目转换为查找图中是否存在正环，采用 DFS 版的 SPFA 。
代码
1 #include<bits/stdc++.h> 2 #define eps 1e-4 3 using namespace std; 4 const int N=3005,M=1e4+5; 5 int n,tot,cnt,hsh[N],fro[N]; 6 double dis[N]; 7 bool vis[N]; 8 char s[1005]; 9 struct edge{int to,w,nxt;}e[M<<1]; 10 void add(int x,int y,int z) { 11 e[++cnt].to=y,e[cnt].w=z,e[cnt].nxt=fro[x]; fro[x]=cnt; 12 } 13 14 bool SPFA(int u,double ave) { 15 vis[u]=1; 16 for(int i=fro[u];i;i=e[i].nxt) { 17 int v=e[i].to; 18 if(dis[v]<dis[u]+e[i].w-ave) { 19 dis[v]=dis[u]+e[i].w-ave; 20 if(vis[v]) return 1; 21 if(SPFA(v,ave)) return 1; 22 } 23 } 24 return vis[u]=0; 25 } 26 27 bool check(double ave) { 28 fill(dis,dis+tot+1,0); 29 fill(vis,vis+tot+1,0); 30 for(int i=1;i<=tot;i++) 31 if(SPFA(i,ave)) return 1; 32 return 0; 33 } 34 35 int main() { 36 while(scanf("%d",&n),n) { 37 tot=cnt=0; 38 memset(hsh,0,sizeof(hsh)); 39 memset(fro,0,sizeof(fro)); 40 for(int i=1;i<=n;i++) { 41 scanf("%s",s); 42 int len=strlen(s); 43 int a=(s[0]-'a')*26+s[1]-'a'; 44 int b=(s[len-2]-'a')*26+s[len-1]-'a'; 45 if(!hsh[a]) hsh[a]=++tot; 46 if(!hsh[b]) hsh[b]=++tot; 47 add(hsh[a],hsh[b],len); 48 } 49 double l=0,r=1e3,ans=-1; 50 while(r-l>eps) { 51 double Mid=(l+r)/2; 52 if(check(Mid)) l=Mid,ans=Mid; 53 else r=Mid; 54 } 55 if(ans==-1) printf("No solution "); 56 else printf("%.2lf ",ans); 57 } 58 }