poj 2049（二分+spfa判负环）

poj 2049（二分+spfa判负环）

首先根据套路，二分是显然的。然后跑一下spfa判断正环就行了。

然而我被no solution坑了十次提交。。

#include <cctype>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn=1e5+5, maxm=1e5+5;

const double eps=1e-4;

struct Graph{

    struct Edge{

        int to, next, v; Graph *bel;

        inline int operator *(){ return to; }

        Edge& operator ++(){

            return *this=bel->edge[next]; }

    };

    void reset(){

        cntedge=0; memset(fir, 0, sizeof(fir)); }

    void addedge(int x, int y, int v){

        Edge &e=edge[++cntedge];

        e.to=y; e.next=fir[x]; e.v=v;

        e.bel=this; fir[x]=cntedge;

    }

    Edge& getlink(int x){ return edge[fir[x]]; }

    //////////

    Edge edge[maxm*2];

    int cntedge, fir[maxn];

}g;

int n, len, visit[maxn];

double dis[maxn], l, r, mid; bool flag;

char s[1005];

int trans(char c1, char c2){

    return (c1-'a')*26+c2-'a'+1; }

bool spfa(int now, double A){

    Graph::Edge e=g.getlink(now); visit[now]=1;

    for (; *e; ++e){

        if (dis[now]+A-e.v<dis[*e]){

            dis[*e]=dis[now]+A-e.v;

            if (visit[*e]||spfa(*e, A)) return true;

        }

    } visit[now]=0;

    return false;

}

int main(){

    for (; scanf("%d", &n), n; ){

        g.reset();

        for (int i=1; i<=n; ++i){

            do{

                fgets(s, 1e5, stdin);

                len=strlen(s);

            }while (len<2);

            g.addedge(trans(s[0], s[1]),

                    trans(s[len-3], s[len-2]), len-1);

        }

        l=0; r=2000;

        while (r-l>eps){

            mid=(l+r)/2; flag=false;

            for (int i=1; i<=26*26; ++i) dis[i]=visit[i]=0;

            for (int i=1; i<=26*26; ++i)

                if (spfa(i, mid)){ flag=true; break; }

            if (flag) l=mid; else r=mid;

        }

        if (r<=eps) printf("No solution.\n");

        else printf("%.3lf\n", (l+r)/2);

    }

    return 0;

}