POJ 3621最適比率生成ループ01スコア計画問題

頂点の重み値の和とエッジの重みの和の比率を最大にするリングを見つけることです.
まず、注意しなければならないのは、問題の要求は任意の点から始めることができ、ネット上の多くの解題報告はデフォルトで1点から始まり、この問題を過ぎたが、明らかに間違っている.
テーマが求めるmaxなので、辺権変形後、SPFAで最長ルートを求め、正ループが現れるかどうかを見て、これに基づいて二分検索を行います.
図がどのように構築されているか分からない場合は、01計画が具体的にどのように行われているかを見てみましょう.

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#define MAXN 1005
#define MAXM 50005
#define INF 1000000000
#define eps 1e-6
using namespace std;
struct node
{
    int v, next;
    double w;
}edge[MAXM];
int head[MAXN], e, vis[MAXN], q[50 * MAXM], c[MAXN];
int n, m;
double d[MAXN], val[MAXN];
void insert(int x, int y, double w)
{
    edge[e].v = y;
    edge[e].w = w;
    edge[e].next = head[x];
    head[x] = e++;
}
bool spfa(double mid)
{
    int h = 0, t = 0;
    for(int i = 1; i <= n; i++)
    {
        vis[i] = c[i] = 1;
        q[t++] = i;
        d[i] = 0;
    }
    while(h < t)
    {
        int u = q[h++];
        vis[u] = 0;
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            double w = val[u] - mid * edge[i].w;
            if(d[v] < d[u] + w)
            {
                d[v] = d[u] + w;
                if(!vis[v])
                {
                    q[t++] = v;
                    vis[v] = 1;
                    c[v]++;
                    if(c[v] > n) return 1;
                }
            }
        }
    }
    return 0;
}
int main()
{
    int x, y;
    double w;
    e = 0;
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%lf", &val[i]);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d%lf", &x, &y, &w);
        insert(x, y, w);
    }
    double low = 0, high = 1000;
    while(high - low > eps)
    {
        double mid = (low + high) / 2;
        if(spfa(mid)) low = mid;
        else high = mid;
    }
    printf("%.2f
", low);
    return 0;
}