传送门

题目描述

给定一张 \(L\) 个点、\(P\) 条边的有向图，每个点都有一个权值 \(f[i]\)，每条边都有一个权值 \(t[i]\)。

求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。

(资料图片仅供参考)

输出这个最大值。

注意：数据保证至少存在一个环。

输入格式

第一行包含两个整数 \(L\) 和 \(P\)。

接下来 \(L\) 行每行一个整数，表示 \(f[i]\)。

再接下来 \(P\) 行，每行三个整数 \(a，b，t[i]\)，表示点 \(a\) 和 \(b\) 之间存在一条边，边的权值为 \(t[i]\)。

解题思路

\(\qquad\)这题要让一个\(\LARGE \frac{\sum f}{\sum t}\)最大化，所以是一个\(01\)分数规划问题，对于\(01\)分数规划，我们可以采用二分求解（实数）。我们二分的目标是最后的答案\(ans\)，在check(x)函数中，有一下\(2\)种情况：

\(\qquad\quad\)\(a.\)当\(mid < ans\)的时候，说明一定有一个环的\(\Large \frac{\sum f}{\sum t} > mid\)，我们对这个公式进一步推导：

\(\qquad\qquad\qquad\qquad\Large \sum f > \sum t \times mid\)

\(\qquad\qquad\qquad\qquad\Large \sum f - \sum t \times mid > 0\)

\(\qquad\qquad\qquad\qquad\Large \sum (f-mid\times t) > 0\)

正好我们这张图有个不好处理的条件，也就是点权，我们在这里只要把点权移到边上，使得每条边的权重变为\(f-mid\times t\)，那我们就可以跑个正环就结束了。这里采用\(dfs\)版的\(SPFA\)判环，实测只要\(20ms\)当然，要跑负环也很容易，只要把上式进行一定的变形：

\(\qquad\qquad\qquad\qquad\Large \sum (mid\times t-f) < 0\)

这样把边权处理成\(mid\times t - f\)就可以跑负环了。

代码

#include #include using namespace std;const int N = 1010, M = 5050;int h[N], e[M], ew[M], vw[N], ne[M], idx;double dist[N]; int st[N], ring, n, m;void add(int a, int b, int c){    e[idx] = b, ne[idx] = h[a], ew[idx] = c, h[a] = idx ++ ;}void dfs(int cur, double x) {    st[cur] = 1;    for (int i = h[cur]; ~i; i = ne[i])     {        int j = e[i]; double w = vw[cur] - ew[i] * x;        if (dist[j] < dist[cur] + w)         {            dist[j] = dist[cur] + w;            if (st[j] == 1) {                ring = true ;                break ;            }            dfs(j, x);            if (ring) return ;        }    }    st[cur] = 114514;}bool check(double x) {    memset(st, 0, sizeof st);    ring = 0;        for (int i = 1; i <= n; i ++ )     {        if (st[i]) continue ;        if (ring) break ;        dfs(i, x);    }        return ring;}int main() {    scanf("%d%d", &n, &m);        for (int i = 1; i <= n; i ++ ) scanf("%d", &vw[i]);        memset(h, -1, sizeof h);    while (m -- )     {        int u, v, w;        scanf("%d%d%d", &u, &v, &w);        add(u, v, w);    }        double l = 1, r = 1000;    while (r - l > 1e-3)     {        double mid = (l + r) / 2;        if (check(mid)) l = mid;        else r = mid;    }    printf("%.2lf\n", l);        return 0;}