地图

Posted on Edited on In

题面大意：Makik 有一张详细的城市地图，地图标注了 L 个景区，编号为 1~L。而景区与景区之间建有单向高速通道。这天，Makik 要去逛景区，他可以任选一个景区开始一天行程，且只能通过单向高速通道进入其他景区。至少要参观两个景区，游玩最后要回到起始景区。 如果 Makik 参观了第 i 个景区，会获得一个乐趣值 F_i。且参观过得景区不会再获得乐趣值。对于第 i 条单向高速通道，需要消耗 T_i 的时间，能够从 L1_i 到达 L2_i。为了简化问题，参观景区不需要花费时间，Makik 想要最终单位时间内获得的乐趣值最大。 请你写个程序，帮 Makik 计算一下他能得到的最大平均乐趣值。

显然我们最终的答案是一个简单环

然后推一下式子：

我们要最大化\[ \dfrac {\sum v_i} {\sum e_i}​\]

不妨让ans就是最大值，所以对于每一个环还可以转化为：

\[\dfrac {\sum v_i} {\sum e_i} \leq ans\]

\[\sum v_i \leq ans \times \sum e_i = \sum (ans \times e_i)\]

\[\sum( v_i - ans \times e_i) \leq 0\]

然后考虑二分，如果图中没有一个正环，说明我们二分出来的足够大了，经过往小里面考虑

用spfa跑正权路，找正环就好

2020.10.23updata补：

其实关于正环负环的我也很蒙逼，感觉我写的也不太对劲

网上找了一篇码风码量都很棒的博客

(我的)代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 66;

int n, m, f[N];
int mark, tag[N];
double dis[N];

inline void build(double ans)
{
    int i, x, y;
    for (x = 1; x <= n; ++ x)
    {
        for (i = head[x]; i; i = nex[i])
        {
            y = ver[i];
            val[i] = len[i] * ans - f[y];
        }
    }
    return;
}

inline void spfa(int x)
{
    tag[x] = 1;
    int i, y;
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        if (dis[y] > dis[x] + val[i])
        {
            if (tag[y]) return (void)(mark = 1);
            dis[y] = dis[x] + val[i];
            spfa(y);
        }
    }
    return (void)(tag[x] = 0);
}

inline bool pd()
{
    int i;
    for (i = 1; i <= n; ++ i) dis[i] = 0, tag[i] = 0;
    mark = 0;
    for (i = 1; i <= n; ++ i)
    {
        spfa(i);
        if (mark) return true;
    }
    return false;
}

signed main()
{
    int i, x, y, z;
    n = read(), m = read();
    for (i = 1; i <= n; ++ i) f[i] = read();
    for (i = 1; i <= m; ++ i)
    {
        x = read(), y = read(), z = read();
        add_edge(x, y, z);
    }

    double l = 0, r = 10000, mid;

    while (r - l > 0.001)
    {
        mid = (l + r) / 2;
        build(mid);
        if (pd()) l = mid;
        else r = mid;
    }

    printf ("%.2lf", l);
    return 0;
}