题解 P3199 【[HNOI2009]最小圈】

std__unsigned · 2017-10-26 12:06:42 · 题解

这道题不容易求出最小值，但我们可以将其化为判断可行性问题，就是二分最小值，用spfa判断负环

注意每次spfa要将vis和dis初始化为0

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const double eps=(1e-9);
int head[10000],n,m,cnt;
bool vis[10000],flag;
double dis[10000];
struct node
{
    int to,w,next;
 } edge[10000];
void add(int u,int v,int w)//加边
{
    cnt++;
    edge[cnt].w=w;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
void spfa(int u,double mid)//dfs版的spfa
{
    vis[u]=1;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(dis[v]>dis[u]+edge[i].w - mid)
        {
            if(vis[v]==1)
            {
                flag=false;    
                return;
            }
            dis[v]=dis[u]+edge[i].w - mid;
            spfa(v,mid);
            if(flag == false) {
                return;
            }
        }
    }
    vis[u]=0;
}
bool judge(double now)//判断
{
    memset(dis,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        if(vis[i]) continue;
        flag=true;
        spfa(i,now);
        if(flag==false)
        return false;
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    double l=0.000000,r=100000.0,mid;
    double result=-1;
    while(l-r<=eps)
    {
        mid=(l+r)/2;
        if(judge(mid)==true) 
        {
            l=mid+eps;    
            result=max(result,mid);
        }
        else r=mid-eps;
    }
    printf("%.8f",mid);
    return 0;
}