POJ-2949 Word Rings (SPFA+二分答案)

传送门

思路：可以把两个字母看成一个点，则最多26^2个点，一个字符串相当于一条权值为它的长度的有向边，建图。枚举答案，将每条边的权值减去这个数，然后SPFA查找图中是否还有正环，二分答案。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

const int MAXN=705;
const double INF=0x3f3f3f3f;
const double eps=1e-3;
int n,m;
bool ff;
char s[10005];
double tt;
struct edge
{
    int v;
    double cost;
    edge(int _v=0,double _cost=0):v(_v),cost(_cost) {}
};
vector<edge>g[MAXN];
void addedge(int u,int v,double w)
{
    g[u].push_back(edge(v,w));
}
bool vis[MAXN];
int cnt[MAXN];
double dist[MAXN];
bool SPFA()
{
    queue<int>que;
    while(!que.empty())que.pop();
    for(int i=0; i<=675; i++)
    {
        vis[i]=false;
        dist[i]=0;
        cnt[i]=1;
        que.push(i);
    }
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int i=0; i<g[u].size(); i++)
        {
            int v=g[u][i].v;
            if(dist[v]<dist[u]+g[u][i].cost-tt)
            {
                dist[v]=dist[u]+g[u][i].cost-tt;
                if(!vis[v])
                {
                    cnt[v]++;
                    //cnt[v]=cnt[u]+1;
                    if(cnt[v]>675)return true;
                    vis[v]=true;
                    que.push(v);
                }
            }
        }
    }
    return false;
}
bool judge(double t)
{
    tt=t;
    bool flag=false;
    flag=SPFA();
    if (flag)
        ff=true;
    return flag;
}
double erf(double l,double r)
{
    double mid=(l+r)/2;
    if (r-l<eps)
        return l;
    if (judge(mid))
        return erf(mid,r);
    else
        return erf(l,mid);
}
int main()
{
    while (~scanf("%d",&n))
    {
        if (n==0)
            break;
        for (int i=0;i<=675;i++)
            g[i].clear();
        int mm=-1;
        for (int i=0;i<n;i++)
        {
            scanf("%s",s);
            int l=strlen(s);
            int a=(s[l-2]-'a')*26+(s[l-1]-'a');
            int b=(s[0]-'a')*26+s[1]-'a';
            mm=max(mm,l);
            addedge(a,b,l);
        }
        ff=false;
        double ans=erf(2,mm);
        if (ff)
            printf("%.2f\n",ans);
        else
            printf("No solution.\n");
    }
    return 0;
}