[BZOJ1486] [HNOI2009] 최소권(01점 계획+spfa 검색)

제목 설명

전송문

문제풀이

01 점수 계획에 마이너스 링이 존재한다면 더 좋은 답이 있다는 뜻이에요.

코드

#include
#include
#include
#include
#include
using namespace std;
#define N 20005

const double eps=1e-9;
const double inf=1e9;
int n,m;
int tot,point[N],nxt[N],v[N];double c[N];
double dis[N],ans;
bool vis[N],flag;

void add(int x,int y,double z)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;
}
void spfa(int x,double mid)
{
    vis[x]=1;
    for (int i=point[x];i;i=nxt[i])
        if (dis[v[i]]>dis[x]+c[i]-mid)
        {
            dis[v[i]]=dis[x]+c[i]-mid;
            if (vis[v[i]])
            {
                flag=1;
                return;
            }
            spfa(v[i],mid);
            if (flag) return;
        }
    vis[x]=0;
}
bool check(double mid)
{
    memset(dis,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;++i)
    {
        flag=0;
        spfa(i,mid);
        if (flag) return 1;
    }
    return 0;
}
double find()
{
    double l=-inf,r=inf,mid,ans=inf;
    while (r-l>eps)
    {
        mid=(l+r)/2.0;
        if (check(mid)) ans=r=mid;
        else l=mid;
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)
    {
        int x,y;double z;scanf("%d%d%lf",&x,&y,&z);
        add(x,y,z);
    }
    ans=find();
    printf("%.8lf
",ans);
}