AcWing361. 观光奶牛

传送门

题目描述

给定一张 \(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 <iostream>
#include <cstring>

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;
}