SPFA找最大比例环#

ans=Σ点权/Σ边权

所以 可以变式为 Σ边权*ans-Σ点权=0

要找出最大的ans 可以二分

边权值变为 目的地点权-ans*边权

检查是否有负环 有则可以更优

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#define CLR(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const int maxn = 5010;

const double EPS = 1e-6;

int n,m,val[maxn],from[maxn],to[maxn],w[maxn];

int head[maxn],tol;

int vis[maxn],c[maxn],d[maxn];

double dis[maxn];

struct edge

{

    int from,to,next;

    double w;

}edge[maxn];

void addedge(int u,int v,double w)

{

    edge[tol].from = u;

    edge[tol].to = v;

    edge[tol].w = w;

    edge[tol].next = head[u];

    head[u] = tol++;

}

void init()

{

    CLR(head,-1);

    CLR(vis,0);

    CLR(c,0);

    CLR(d,0);

    for(int i = 0; i <= n; i++) dis[i] = 1000001;

    tol = 0;

}

bool check(double ans)

{

    init();

    for(int i = 1; i <= m; i++){

        int u = from[i];

        int v = to[i];

        addedge(u,v,(1.0*val[v] - 1.0*w[i]*ans)*-1);

        d[u]++;

    }

    for(int i = 1; i <= n; i++){

        if(d[i] == 0) addedge(0,i,0);

    }

    addedge(0,1,0);

    queue<int> q;

    q.push(0);

    dis[0] = 0;

    while(!q.empty()){

        int u = q.front();

        q.pop();

        vis[u] = 0;

        for(int i = head[u]; ~i; i = edge[i].next){

            int v = edge[i].to;

            double W = edge[i].w;

            if(dis[u] + W < dis[v]){

                dis[v] = W + dis[u];

                if(!vis[v]){

                    vis[v] = 1;

                    c[v]++;

                    if(c[v] > n){

                        return false;

                    }

                    q.push(v);

                }

            }

        }

    }

    return true;

}

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",&from[i],&to[i],&w[i]);

    }

    double l = 0;

    double r = 1000001;

    while( r - l > EPS){

        double mid = (l + r) / 2;

        if(check(mid))

            r = mid;

        else

            l = mid;

    }

    printf("%.2f\n",r);

    return 0;

}