bzoj千题计划227：bzoj1486: [HNOI2009]最小圈

http://www.lydsy.com/JudgeOnline/problem.php?id=1486

二分答案

dfs版spfa判负环

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#define N 3001

#define M 10001

using namespace std;

int n;

int tot,front[N],nxt[M],to[M];

double val[M];

double Val[M];

double dis[N];

bool vis[N];

bool tag;

queue<int>q;

int s;

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void add(int u,int v,double w)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;

}

void spfa(int u)

{

    //if(tag) return;

    int t;

    for(int i=front[u];i;i=nxt[i])

    {

        t=to[i];

        if(dis[u]+Val[i]<dis[t])

        {

            dis[t]=dis[u]+Val[i];

            if(!vis[t])

            {

                vis[t]=true;

                spfa(t);

                vis[t]=false;

                if(tag) return;

            }

            else

            {

                tag=true;

                return;

            }

        }

    }

}

bool check(double mid)

{

    for(int i=;i<=tot;++i) Val[i]=val[i]-mid;

    tag=false;

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

    {

        for(int j=;j<=n;++j) dis[j]=;

        vis[i]=true;

        spfa(i);

        vis[i]=false;

        if(tag) return true;

    }

    return false;

}

int main()

{

    int m;

    read(n); read(m);

    int u,v; double w;

    while(m--)

    {

        read(u); read(v); scanf("%lf",&w);

        add(u,v,w);

    }

    double l=-1e6,r=1e6,mid,ans;

    int T=;

    while(T--)

    {

        mid=(l+r)/;

        if(!check(mid)) ans=l,l=mid;

        else r=mid;

    }

    printf("%.8lf",ans);

}

1486: [HNOI2009]最小圈

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 2715  Solved: 1304
[Submit][Status][Discuss]

Description

Input

 

Output

 

Sample Input

4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3

Sample Output

3.66666667