01分数规划

01分数规划

二分答案。设二分的值为实数mid。

• 如果途中存在一个环S，使得 \(Σ(mid * wt[j]-wf[t])<0\) ，那么我们可知：
  存在一个 \(S\) ，使得 \(mid<\frac{Σwf}{Σwt}\)
  也即是说，本题所求的最大值一定大于 \(mid\) 。

• 如果对图中任意一个环 \(S\) ，都有 \(Σ(mid * wt[j]-wf[t])>=0\) ，同理可知：
  所有的 \(S\) ，都有 \(mid>=\frac{Σwf}{Σwt}\)
  也就是说，本题所求的最大值不超过 mid。

综上所述对于每轮二分，我们建立一张新图，结构与原图相同，但是没有点权，有向边的权值是 \(mid * wt[j] - wf[t]\) ，即本来的边权乘上 \(mid\) 再减去入点的权值。

在这张新图上，\(Σ(mid * wt[j] - wf[t])<0\) 的含义就是图中存在负环。因此，我们用 \(SPFA\) 算法在新图上求最短路，若有负环，说明 \(mid\) 比答案小，应该令 \(l=mid\) 。若最短路的求解正常结束，则令 \(r=mid\) 。二分结束时就求出了本题的答案。

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010, M = 5010;

int h[N], e[M], ne[M], wt[M], idx;
int wf[N], cnt[N];
double dist[N];
int n, m;
bool st[N];

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

bool check(double mid) 
{
    queue<int> q;
    for (int i = 1; i <= n; i ++ ) q.push(i), st[i] = true;
    memset(cnt, 0, sizeof cnt);

    while (q.size()) 
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i]) 
        {
            int j = e[i];
            if (dist[j] > dist[t] + mid * wt[i] - wf[t]) 
            {
                dist[j] = dist[t] + mid * wt[i] - wf[t];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) 
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

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

    for (int i = 1; i <= n; i ++ ) cin >> wf[i];
    while (m -- ) 
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    double l = 0, r = 1000; // 01分数规划
    while (r - l > 1e-4) 
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%.2lf", r);

    return 0;
}

01分数规划

原文：https://www.cnblogs.com/wanshu/p/14715482.html