spfa判断负环+01分数规划

解题报告：二分他们的商值，把每条边变成t[i]-mid*w[i]，然后看是否存在正环。

#include<bits/stdc++.h>
using namespace std;
const   int N= 1010 ,M=5010;
int h[N],idx,e[M],ne[M];
double t[N],w[M];
 int n,m;
 int q[N];
 double dist[N];
 int cnt[N];
 bool st[N];
 void add(int a,int b,int c)
 {
   
  e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;   
 }
 bool check(double mid)
 {
    
     int tt=0,hh=0;
     memset(st,0,sizeof st);
     memset(cnt,0,sizeof cnt);
     for(int i=1;i<=n;i++)
    {
   
        q[tt++]=i;
        st[i]=true;
    }
   // cout<<mid<<endl;
    while(tt!=hh)
    {
   
        int t1=q[hh++];
        if(hh==N)   hh=0;
        st[t1]=false;
        for(int i=h[t1];~i;i=ne[i])
        {
   
            int j=e[i];
            if(dist[j] < dist[t1]+t[t1]-mid*w[i])
            {
   
                dist[j] =dist[t1]+t[t1]-mid*w[i];
                cnt[j]=cnt[t1] +1;
                if(cnt[j]>=n)   return true;
                if(!st[j])
                {
   
                    st[j]=true;
                    q[tt++]=j;
                    if(tt==N)   tt=0;
                }
            }
        }
    }
    return false;
 }
int main()
{
   
   memset(h,-1,sizeof h);
   cin >> n >> m;
   for(int i=1;i<=n;i++)
   cin >> t[i];
   while(m--)
   {
   
       int a,b,c;
       cin>>a>>b>>c;
       add(a,b,c);
       //add(b,a,c);
   }
    double l = 0 ,r=1000;
    while(r-l>1e-5)
    {
   
        double  mid= (l+r)/2;
        if(check(mid))
        l=mid;
        else
        r=mid;
    }
    printf("%.2lf\n",l);
    return 0;
}