[JZOJ3852] 单词接龙

Description

Bsny从字典挑出N个单词，并设计了接龙游戏，只要一个单词的最后两个字母和另一个单词的前两个字母相同，那么这两个单词就可以有序的连接起来。
Bsny想要知道在所给的所有单词中能否按照上述方式接龙组成一个单词环（可能是多个），若能，求所有环的环中单词平均长度最大值。
20%的数据：n≤20；
70%的数据：n≤1000；
100%的数据：n≤100000，每个单词长度不超过1000。输入数据比较大，C/C++的同学用scanf输入。

Solution

事实上，我们发现一个单词有用的只有长度为2的前后缀以及单词的长。

既然是环，那就要连边在图上做。然而我们发现单词数太多，因此考虑将前后缀作为点，单词作为有向边，长度作为边权。

又发现它是平均数，因此考虑二分答案，将每条边减掉边权，寻找正环。
SPFA跑最长路判环即可。

注意特判不能走同一条边，否则会出现一个单词头尾相连的情况。

Code

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
#define LL long long
#define dl double
#define INF -10007
using namespace std;
int m,n,n1,a[20*N][2],fs[N],nt[5*N],dt[5*N],vl,d[N],ti[N],num;
dl pr[N],dis[N];
bool bz[N],b[N];
void link(int x,int y,int z)
{
    nt[++m]=fs[x];
    dt[m]=y;
    fs[x]=m;
    pr[m]=z;
}
bool pd(dl lim)
{
    memset(bz,0,sizeof(bz));
    memset(dis,128,sizeof(dis));
    memset(d,0,sizeof(d));
    memset(ti,0,sizeof(ti));
    int l=0,r=1;
    d[r]=1;
    dis[1]=0;
    ti[1]=1;
    bz[1]=1;
    while(l<r)
    {
        int k=d[++l];
        for(int i=fs[k];i;i=nt[i])
        {
            int p=dt[i];
            if(dis[p]<dis[k]+pr[i]-(k!=1)*lim)
            {
                if(ti[p]>num) return 1;
                else dis[p]=dis[k]+pr[i]-(k!=1)*lim,d[++r]=p,bz[p]=1,ti[p]++;
            }
        }
        bz[k]=0;
    }
    return 0;
}
int main()
{   
    cin>>n;
    char ch[1005];
    dl lf=0,ri=0;
    n1=0;
    memset(b,0,sizeof(b));
    fo(i,1,n)
    {
        scanf("%s",ch+1);
        int l=strlen(ch+1);
        ri=max(ri,(dl)l);
        a[i][0]=(ch[1]-'a'+1)*100+ch[2]-'a'+1;
        a[i][1]=(ch[l-1]-'a'+1)*100+ch[l]-'a'+1;
        link(a[i][0],a[i][1],l);
        n1=max(n1,max(a[i][0],a[i][1]));
        if(b[a[i][0]]==0) link(1,a[i][0],0),b[a[i][0]]=1,num++;
        if(b[a[i][1]]==0) link(1,a[i][1],0),b[a[i][1]]=1,num++;
    }
    while(lf<ri-0.001)
    {
        dl mid=(lf+ri)/2;
        if(pd(mid)) lf=mid;
        else ri=mid;
    }
    if(pd(ri)) printf("%.2lf",ri);
    else if(lf!=0) printf("%.2lf",lf);
    else printf("No solution.");
}