题意：给定N个字符串，如果A串的最后两个字母跟B串的前两个字母相同它们就能连接。
求一个由字符串组成的首尾相连的环，使（字符串总长度/字符串个数）最大。
n<=100000 len<=1000
思路：SPFA国家队论文题
赋所有dis[i]=0，跑最长路，如果某个元素入队次数超过点数就说明有正环。
使用DFS版本的SPFA做比BFS快10倍，为什么？
论文里高大上看不懂，蒟蒻用简单粗暴的方法想了一下：
如果某个环有K个点组成，BFS会从K个点中的某个点开始，每次都换一个点扩展一次，可能达到O（N*K^2）
DFS则只选其中的一个点不断扩展，K次就能使自己重新入队一次，这样就是O（N*K）
孰优孰劣一眼分明
以下是论文原文，用来证明初始值=0的正确性
var q:array[..]of longint;
dis:array[..]of double;
head,vet,next,len,time,inq:array[..]of longint;
n,m,tot,i,x,y,k:longint;
l,r,mid,last,eps:double;
ch:ansistring; procedure add(a,b,c:longint);
begin
inc(tot);
next[tot]:=head[a];
vet[tot]:=b;
len[tot]:=c;
head[a]:=tot;
end; function spfa(k:double):boolean;
var u,top,i,e,v:longint;
begin
top:=;
for i:= to * do
begin
inq[i]:=; dis[i]:=; time[i]:=;
end;
for i:= to * do
if head[i]> then
begin
inc(top); q[top]:=i; inq[i]:=; inc(time[i]);
end;
while top> do
begin
u:=q[top]; dec(top);
inq[u]:=;
e:=head[u];
while e<> do
begin
v:=vet[e];
if dis[u]+len[e]-k>dis[v] then
begin
dis[v]:=dis[u]+len[e]-k;
if inq[v]= then
begin
inc(top); q[top]:=v; inq[v]:=;
inc(time[v]);
if time[v]>n then exit(true);
end;
end;
e:=next[e];
end;
end;
exit(false);
end; begin
assign(input,'poj2949.in'); reset(input);
assign(output,'poj2949.out'); rewrite(output);
while not eof do
begin
readln(n);
if n= then exit;
fillchar(head,sizeof(head),); tot:=;
for i:= to n do
begin
readln(ch); k:=length(ch);
x:=(ord(ch[])-ord('a'))*+ord(ch[])-ord('a')+;
y:=(ord(ch[k-])-ord('a'))*+ord(ch[k])-ord('a')+;
add(x,y,k);
end;
n:=;
for i:= to * do
if head[i]> then inc(n);
l:=; r:=; last:=;
eps:=1e-5;
while r-l>eps do
begin
mid:=(l+r)/;
if spfa(mid) then begin last:=mid; l:=mid; end
else r:=mid;
end;
if last<eps then writeln('No solution.')
else writeln(last::); end;
close(input);
close(output);
end.
