spfa找负(正)环

把每个点的点权放到它的出边上，
问题转化为在一个环上：
∑(pw[i]/w[i]) >=mid
∑pw[i] - mid∑w[i] >=0
∑(pw[i]-midw[i]) >=0
找mid，边权为pw[i]-mid*w[i]，有正换

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1025;
const int M=5010;
int h[N],e[M],ne[M],st[N],idx;
int w[M];
double dist[N];
int pw[N];
int n,m;
int cnt[N];


void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int check(double mid)
{
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);

    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        q.push(i);
        st[i]=1;
    }
    while(q.size())
    {
        int t=q.front();
        //cout<<"a"<<endl;
        q.pop();
        st[t]=0;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]<dist[t]+pw[t]-mid*w[i])
            {
                dist[j]=dist[t]+pw[t]-mid*w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return 1;
                if(!st[j])
                {
                    st[j]=1;
                    q.push(j);
                }
            }

        }
    }
    return 0;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);

    for(int i=1;i<=n;i++)
    {
        cin>>pw[i];
    }

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }


    //把每条边的权重，变成 点权-mid*边权
    double l=0,r=1010;
    //保留两位小数的做法！！
    while(r-l>1e-4)
    {
        double mid=(l+r)/2;
        //我们的目的是找最大的mid,mid越大，check越容易失败，如果check成功，说明mid还可以更大 
        if(check(mid)) l=mid;
        else r=mid;
    }

    printf("%.2lf",r);
    return 0;
}

这题很nb，转换成求负环或正环的问题，需要再次复习

具体思路如下
1. 首先要确定是找正环还是负环，一刷的时候写的是正环的思路，现在写一下负环的。理解过程如下

我们假设最大值，即答案为ans。
如果 mid <=ans，说明存在一个环,使得f/w>=mid, 也就是说mid*w-f<=0,也就是说存在一个负环。
所以得出：mid<=ans，有负环，mid要放大
所以在spfa中，更新dist[j]的方式为：

if(dist[j]>dist[u]-f[u]+cost*w[i])
    dist[j]=dist[u]-f[u]+cost*w[i];

而且有负环返回1，mid要放大；无负环返回0，mid要缩小

还有一点需要注意，因为保留两位小数，二分时要写成r-l>1e-4 才够精度

#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>

using namespace std;

const int N=10010;

int e[N],ne[N],idx,h[N],st[N];
double w[N],f[N];

double dist[N];
int cnt[N];
int n,m;

void add(int a,int b,double c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int spfa(double cost)
{
    memset(dist,0,sizeof dist);
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
    queue<int> q;

    for(int i=1;i<=n;i++)
    {
        st[i]=1;
        q.push(i);
    }

    while(q.size())
    {
        int u=q.front();
        q.pop();
        st[u]=0;

        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j=e[i];

            if(dist[j]>dist[u]-f[u]+cost*w[i])
            {
                dist[j]=dist[u]-f[u]+cost*w[i];
                cnt[j]=cnt[u]+1;
                if(cnt[j]>n) return 1;
                if(!st[j])
                {
                    st[j]=1;
                    q.push(j);
                }
            }
        }
    }
    //cost越大，越有可能有负环，没有负环说明cost可以继续增大
    return 0;

}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    {
        cin>>f[i];
    }
    for(int i=1;i<=m;i++)
    {
        int a,b;
        double c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    double l=0,r=10101;
    while(r-l>1e-4)
    {
        double mid=(l+r)/2.0;
        //若mid<=ans，说明存在一个环使得：f/w >=mid, mid*w-f<=0，存在负环，说明存在负环的话，mid可以继续增大
        if(spfa(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf",r);

    return 0;
}