POJ3621最優比率生成環 01分數規劃問題

題目大意就是找到一個環使得頂點權值之和與邊權之和的比率最大
首先，需要注意的是題目要求可以從任意一點開始，網上很多解題報告默認的從1點開始，雖然過了此題，但是顯然是不太對的
由於題目是求的max，那麼在邊權變形後，用 SPFA求最長路，看是否出現正環， 然後根據這個進行二分查找。
如果不懂圖是怎麼構建的，可以看一下01規劃具體是怎麼做的。

[cpp]
#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) 
{    www.2cto.com
    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\n", low); 
    return 0; 
}