题解：观光奶牛问题

一、题目背景

给定一个有 (L) 个点、(P) 条边的有向图，每个点有权值 (f[i])，每条边有权值 (t[i])。需要在图中找到一个环，使得环上各点的权值之和除以环上各边的权值之和最大，并输出这个最大值。

二、解题思路

本题采用二分答案和SPFA算法结合的方式求解。由于直接求最优解比较困难，所以通过二分答案的方法，不断逼近最优值。对于每个二分得到的中间值 (mid)，利用SPFA算法判断图中是否存在满足条件的环。

具体步骤如下：
1. 定义图的存储结构，包括点权数组、邻接表相关数组、距离数组、队列数组、记录每个节点入队次数的数组以及节点是否在队列中的标记数组。
2. 编写添加边的函数，用于构建邻接表。
3. 实现检查函数 check，对于给定的中间值 (mid)，利用SPFA算法判断图中是否存在一个环，使得环上点权和减去 (mid) 乘以环上边权和大于0（即满足条件的环）。
4. 在 main 函数中：
- 读取点的数量 (n) 和边的数量 (m)，以及每个点的权值。
- 初始化邻接表，读取每条边的信息并添加到邻接表中。
- 设定二分的范围，左边界 (l = 0)，右边界 (r = 1e6)。
- 进行二分查找，每次计算中间值 (mid)，调用 check 函数判断是否存在满足条件的环，根据结果调整二分的范围。
- 当二分范围足够小（(r - l > 1e-4)）时，输出左边界 (l) 作为结果，保留两位小数。

三、代码逐段分析

（一）头文件和全局变量

#include <cstring>
#include <iostream>
#include <algorithm>

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

1. 头文件：
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 常量定义：
   • const int N = 1010, M = 5010;：定义点的最大数量和边的最大数量。
3. 变量定义：
   • int n, m;：分别表示点的数量和边的数量。
   • int wf[N];：数组 wf 存储每个点的权值。
   • int h[N], e[M], wt[M], ne[M], idx;：邻接表相关数组，h[N] 存储每个点的头指针，e[M] 存储边的终点，wt[M] 存储边权，ne[M] 存储下一条边的指针，idx 用于边的编号。
   • double dist[N];：记录从源点到每个节点的距离（这里距离的含义根据 check 函数中的计算而定）。
   • int q[N], cnt[N];：q[N] 是队列数组，用于SPFA算法；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 ++ ;
}

该函数用于向邻接表中添加一条边，参数 a 为起点，b 为终点，c 为边权。通过更新邻接表数组，将边的信息存储起来。

（三）检查函数

bool check(double mid)
{
    memset(dist, 0, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        q[tt ++ ] = i;
        st[i] = true;
    }

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; 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[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

1. 初始化：
   • memset(dist, 0, sizeof dist);：将距离数组初始化为0。
   • memset(st, 0, sizeof st);：将节点在队列中的标记初始化为 false。
   • memset(cnt, 0, sizeof cnt);：将每个节点的入队次数初始化为0。
2. 入队操作：
   • 将所有节点入队，标记为在队列中。
3. 队列处理：
   • 当队列不为空时，取出队头节点 t，标记为不在队列中。
   • 遍历节点 t 的所有邻接边，如果通过节点 t 到邻接节点 j 的距离更短（这里的距离计算为 dist[t] + wf[t] - mid * wt[i]），则更新距离 dist[j]，入队次数 cnt[j] 加1。
   • 如果某个节点的入队次数 cnt[j] 达到节点总数 n，说明存在满足条件的环（即存在负权回路，这里的负权是根据计算规则定义的），返回 true。
   • 如果邻接节点 j 不在队列中，则将其入队并标记为在队列中。
4. 返回结果：
   • 遍历完所有边后，若没有发现满足条件的环，返回 false。

（四）main 函数

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

1. 读取数据并初始化：
   • cin >> n >> m;：读取点的数量 n 和边的数量 m。
   • 通过循环读取每个点的权值并存储到 wf 数组中。
   • memset(h, -1, sizeof h);：初始化邻接表头指针数组为 -1。
   • 通过循环读取每条边的信息（起点、终点和边权），并调用 add 函数添加到邻接表中。
2. 二分查找：
   • 设定二分的左边界 l = 0，右边界 r = 1e6。
   • 当 r - l > 1e-4 时，进行循环：
     • 计算中间值 mid = (l + r) / 2。
     • 调用 check 函数判断是否存在满足条件的环，如果存在，则更新左边界 l = mid；否则更新右边界 r = mid。
3. 输出结果并结束程序：
   • printf("%.2lf\n", l);：输出最终结果，保留两位小数。
   • return 0;：程序正常结束。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 输入和建图：读取点权和边的信息并构建邻接表，时间复杂度为 (O(n + m))，其中 (n) 是点的数量，(m) 是边的数量。
2. 二分查找：二分的次数大约为 (O(\log(1e6 / 1e-4)) = O(20)) 次，每次二分调用 check 函数。
3. check 函数（SPFA算法）：在最坏情况下，每个节点都可能入队 (n) 次，每次入队处理其邻接边，时间复杂度为 (O(nm))。
   总体时间复杂度为 (O(20 \times nm + n + m) = O(nm))，主要由 check 函数的时间复杂度决定。

（二）空间复杂度

1. 邻接表：存储边的信息，空间复杂度为 (O(m))。
2. 其他数组：点权数组 wf[N]、距离数组 dist[N]、队列数组 q[N]、入队次数数组 cnt[N] 和标记数组 st[N]，空间复杂度均为 (O(n))。
   总体空间复杂度为 (O(n + m))。

希望这份题解能帮助你理解这道题的解题思路和代码实现。如果有任何疑问，欢迎随时提问。