POJ 3621 Sightseeing Cows：最優比率環的 0-1 分數規劃 + SPFA 判負環

問題重述

有向圖 n≤1000, m≤5000。每點有點權 v_i，每邊有邊權 e_i。求一個環，使 (環上點權和) / (環上邊權和) 最大。輸出最大比值（保留兩位小數）。

分數規劃轉參數化判定

設比值為 λ。對每條邊 u→v，定義新權 w' = λ·e - v（注意：點權歸屬於終點）。
環 C 的新權和 = Σ(λ·e_i - v_i) = λ·Σe_i - Σv_i。
若存在 負權環（新權和 < 0），則 λ·Σe < Σv ⇒ λ < Σv/Σe，說明 λ 偏小。
若無負權環，則 λ ≥ Σv/Σe 對所有環成立，λ 偏大或最優。
故二分 λ，每次跑 SPFA 判負環。

SPFA 判負環模板

bool hasNegativeCycle(double lambda) {
    vector dist(n+1, 0);
    vector cnt(n+1, 1), inq(n+1, 1);
    queue q;
    for(int i=1;i<=n;++i) q.push(i); // 超級源點等價：全點入隊

    while(!q.empty()) {
        int u=q.front(); q.pop(); inq[u]=0;
        for(auto &ed: adj[u]) {
            int v=ed.v;
            double w = ed.w * lambda - val[v]; // 新權
            if(dist[v] > dist[u] + w + 1e-9) {
                dist[v] = dist[u] + w;
                if(!inq[v]) {
                    inq[v]=1; q.push(v);
                    if(++cnt[v] > n) return true; // 負環
                }
            }
        }
    }
    return false;
}

完整 C++ 代碼

#include 
using namespace std;
const double EPS = 1e-7;

struct Edge { int v; double w; };
int n, m;
int val[1005];
vector adj[1005];

bool spfa(double mid) {
    vector dis(n+1, 0);
    vector cnt(n+1, 1), inq(n+1, 1);
    queue q;
    for(int i=1;i<=n;++i) q.push(i);

    while(!q.empty()) {
        int u=q.front(); q.pop(); inq[u]=0;
        for(auto &e: adj[u]) {
            int v=e.v;
            double w = e.w * mid - val[v];
            if(dis[v] > dis[u] + w + EPS) {
                dis[v] = dis[u] + w;
                if(!inq[v]) {
                    inq[v]=1; q.push(v);
                    if(++cnt[v] > n) return true;
                }
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while(cin >> n >> m) {
        for(int i=1;i<=n;++i) { cin >> val[i]; adj[i].clear(); }
        for(int i=0;i> u >> v >> w;
            adj[u].push_back({v,w});
        }
        double L=0, R=1000; // 點權≤1000, 邊權≥1, 比值上界 1000
        while(R - L > EPS) {
            double mid=(L+R)/2;
            if(spfa(mid)) L=mid; else R=mid;
        }
        cout << fixed << setprecision(2) << L << '\n';
    }
    return 0;
}

關鍵細節

1. 點權歸屬：新權 λ·e - v 中 v 是**終點**點權，保證環上每個點權被扣一次。
2. 超級源點技巧：全點初始入隊、dis=0、cnt=1，等價於添加虛擬源點連向所有點權 0 邊，檢測全圖負環。
3. 浮點比較：dis[v] > dis[u] + w + EPS 避免精度抖動導致誤判負環。
4. 二分上界：點權 ≤ 1000，邊權 ≥ 1，最大比值 ≤ 1000，設 R=1000 保险。

複雜度

• SPFA 平均 O(m)，最壞 O(nm)，但隨機圖極快。
• 二分 ~30 次，總體 < 1s。

相關問題

• 最優比率生成樹（Karp/二分+最小生成樹）。
• 最優比率路徑（二分+SPFA/Bellman-Ford）。
• 本題為「最優比率環」經典模板題。