BZOJ 1690 奶牛的旅行

分数规划。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxv 1050
#define maxe 10050
#define inf 2000000000
#define eps 1e-3
using namespace std;
int n,m,val[maxv],nume=1,g[maxv],x,y,z,flag=0;
struct edge
{
    int v,c,nxt;
    double w;
}e[maxe];
double dis[maxv];
bool vis[maxv];
void addedge(int u,int v,int c)
{
    e[++nume].v=v;e[nume].c=c;
    e[nume].nxt=g[u];g[u]=nume;
}
void rebuild(double x)
{
    for (int i=2;i<=nume;i++)
        e[i].w=e[i].c*x-val[e[i].v];
}
void spfa(int x)
{
    vis[x]=true;
    for (int i=g[x];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if (dis[v]>dis[x]+e[i].w)
        {
            if (vis[v]) {flag=1;break;}
            else {dis[v]=dis[x]+e[i].w;spfa(v);}
        }
    }
    vis[x]=false;
}
bool check(double x)
{
    rebuild(x);
    for (int i=1;i<=n;i++) dis[i]=inf;
    dis[1]=-val[1];flag=0;spfa(1);
    return flag;
}
void binary_search()
{
    double l=0,r=inf,ans;
    while (r-l>=eps)
    {
        double mid=(l+r)/2;
        if (check(mid)) {ans=mid;l=mid;}
        else r=mid; 
    }
    printf("%.2lf
",ans);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&val[i]);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
    }
    binary_search();
    return 0;
}