spfa判断正环

spfa判断正环

Word Rings 二分+判断正环

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 100000+5;
vector<pair<int,int> >e[maxn];
map<string,int>mp;
double d[maxn];
int inq[maxn],cnt,n;
bool dfs(int u,double avg)
{
    inq[u]=1;
    for(int i = 0;i<e[u].size();i++)
    {
        int v = e[u][i].first;
        if(d[v]<d[u]+e[u][i].second-avg)
        {
            d[v]=d[u]+e[u][i].second-avg;
            if(inq[v]||dfs(v,avg))
                return true;
        }
    }
    inq[u]=0;
    return false;
}
bool check(double avg)
{
    memset(d,0,sizeof(d));
    memset(inq,0,sizeof(inq));
    for(int i = 1;i<=n;i++)
        if(dfs(i,avg))return true;
    return false;
}
int main()
{
    while(scanf("%d",&n)!=EOF && n)
    {
        for(int i=0;i<=n;i++)
            e[i].clear();
        //mp.clear();
        string s;cnt=1;
        for(int i = 0;i<n;i++)
        {
            string tmp=""; 
            cin >> s;
            tmp+=s[0];
            tmp+=s[1];
            if(!mp.count(tmp))
                mp[tmp]=cnt++;
            string tmp1="";
            tmp1+=s[s.size()-2];
            tmp1+=s[s.size()-1];
            if(!mp.count(tmp1))
                mp[tmp1]=cnt++;
            e[mp[tmp]].push_back(make_pair(mp[tmp1],s.size()));
        }
        n = mp.size();
        double ans = -1;
        double l = 0,r=1000;
        for(int i = 0;i<100;i++)
        {
            double mid = (l+r)/2;
            if(check(mid))
                l=mid,ans=mid;
            else
                r=mid;
        }
        if(ans==-1)
            printf("No solution.\n");
        else
            printf("%.2f\n",ans);
    }
}