题解 P3199 【[HNOI2009]最小圈】

Position · 2017-07-22 15:03:15 · 题解

二分答案+dfs spfa判负环

二分出一个答案mid，对于每条边的权值减去mid，利用spfa找负环，如果找到的话，说明mid可作为最小圈的平均值

对于判负环，dfs的spfa比bfs的快很多

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 3005
#define maxe 10005
using namespace std;
struct Edge
{
    int v;
    double w;
    int next;
}e[maxe];
int head[maxn],cnts=0,n,m;
double eps=1e-9,dis[maxn];
bool vis[maxn],flag;
inline void addedge(int u,int v,double w)
{
    cnts++;
    e[cnts].v=v;
    e[cnts].w=w;
    e[cnts].next=head[u];
    head[u]=cnts;
}
void spfa(int x,double mid)
{
    vis[x]=1;
    for(int i=head[x];i!=0;i=e[i].next)
    {
        int v=e[i].v;
        if(dis[v]>dis[x]+e[i].w-mid)
        {
            if(vis[v])
            {
                flag=1;
                return;
            }
            dis[v]=dis[x]+e[i].w-mid;
            spfa(v,mid);
        }
    }
    vis[x]=0;
}
inline bool check(double mid)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    for(int i=1;i<=n;i++)
    {
        flag=0;
        spfa(i,mid);
        if(flag) return 1;
    }
    return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++)
    {
        double w;
        scanf("%d%d%lf",&u,&v,&w);
        addedge(u,v,w);
    }
    double l=-1e5,r=1e5,mid;
    while(r-l>eps)
    {
        mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    printf("%.8lf",mid);
}