0/1分数规划详解

题意

$\space\space\space\space\space$ 判断图上一个环上的最大比值问题

思路

1. 首先我们明确这是个0/1规划问题 那么我们可以进行二分答案枚举
2. 通过二分答案来枚举最大的比值 通过spfa来判断是否是正环即可

过程证明推导思路不在赘述 详情看0/1分数规划详解

$\space\space\space\space\space$ 那么我们只需要判断
$$ {\sum_{i = 1}^{n}(f_i - mid * t_i)} \geq 0$$
$\space\space\space\space\space$ 我们可以将给比值映射到点权上 再对边的枚举情况时候进行比较 我们发现 本题是求最大值 即在满足大于等于0的基础上的最大值 显然我们需要的是一个正环 而判断正环的方法恰好与负环相等 我们只需要仅仅将枚举最短路->最长路即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

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

void add(int a, int b, int c)
{
    e[idx] = b, wt[idx] = c, ne[idx] = h[a], h[a] = idx ++; 
}
void init()
{
    memset(dist, 0, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
}

bool check(double mid)
{
    init();
    queue<int>q;

    for(int i = 1; i <= n; i ++)
    {
        q.push(i);
        st[i] = true;
    }

    while(q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] < dist[t] + wf[t] - mid * wt[i]) //因为我们需要的是正环 所以改正求最长路问题
            {
                dist[j] = dist[t] + wf[t] - mid * wt[i];
                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;
    for(int i = 1; i <= n; i ++) cin >> wf[i];

    memset(h, -1, sizeof h);
    for(int j = 0; j < m; j ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    double l = 0, r = 1e6;
    while(r - l > 1e-4)
    {
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2lf\n", l);
    return 0;

}