bzoj 1486: [HNOI2009]最小圈 dfs求负环

1486: [HNOI2009]最小圈

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1022  Solved: 487
[Submit][Status]

Description

　　最开始写floyd求负环结果TLE了，改成dfs后速度变成原来的100+倍。反正还是比较神奇。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 4000

#define MAXE 50000

#define MAXV 10000

#define PROB "loop"

#define eps 1e-4

#define INF 0x3f3f3f3f3f3f3f3fLL

#define inf 1E1000

#ifdef unix

#define LL "%lld"

#else

#define LL "%I64d"

#endif

typedef long long qword;

typedef long double real;

struct edge

{

        int x,y;

        real z;

}el[MAXE];

struct Edge

{

        int np;

        real val;

        Edge *next;

}E[MAXE],*V[MAXV];

int tope=-;

void addedge(int x,int y,real z)

{

        E[++tope].np=y;

        E[tope].val=z;

        E[tope].next=V[x];

        V[x]=&E[tope];

}

bool state[MAXN];

real dst[MAXN];

bool dfs(int now)

{

        Edge *ne;

        state[now]=true;

        for (ne=V[now];ne;ne=ne->next)

        {

                if (dst[ne->np]>dst[now]+ne->val)

                {

                        if (state[ne->np])return true;

                        dst[ne->np]=dst[now]+ne->val;

                        if (dfs(ne->np))return true;

                }

        }

        state[now]=false;

        return false;

}

int main()

{

      //  freopen(PROB".in","r",stdin);

        //freopen(PROB".out","w",stdout);

        freopen("input.txt","r",stdin);

        int n,m;

        scanf("%d%d",&n,&m);

        int i,j,k,x,y;

        real z;

        real l,r,mid;

        l=r=;

        for (i=;i<m;i++)

        {

                scanf("%d%d%Lf",&x,&y,&z);

                x--;y--;

                addedge(x,y,z);

        //        addedge(y,x,z);

                if(z<)l+=z;

                else r+=z;

        }

        bool flag;

        while (l+1e-<r)

        {

                mid=(l+r)/;

                for (i=;i<=n;i++)dst[i]=,state[i]=false;;

                flag=false;

                for (i=;i<=tope;i++)E[i].val-=mid;

                for (i=;i<=n;i++)

                {

                        if (dfs(i))

                        {

                                flag=true;

                                break;

                        }

                }

                for(i=;i<=tope;i++)E[i].val+=mid;

                if (flag)

                {

                        r=mid;

                }else

                {

                        l=mid;

                }

        }

        printf("%.8Lf\n",(real)r);

}