题解：糖果分配问题

一、题目背景

幼儿园有 (N) 个小朋友，老师要给每个小朋友分配糖果，同时要满足小朋友们提出的 (K) 个要求。这些要求包括小朋友之间糖果数量相等、一个小朋友的糖果数量少于另一个等情况。老师需要知道至少准备多少糖果，才能既满足每个小朋友都有糖果，又满足所有要求。

二、解题思路

本题可通过构建有向图，并利用SPFA算法求解。将每个小朋友看作图中的一个节点，根据小朋友之间的糖果数量关系构建边。然后利用超级源点（编号为 (0) 的节点）与所有小朋友节点相连，确保每个小朋友都能分配到糖果（至少为 (1) 颗）。最后通过SPFA算法判断图中是否存在负权回路（如果存在则无解），并计算出满足条件下每个小朋友最少能得到的糖果数，将这些糖果数相加得到结果。

具体步骤如下：
1. 定义图的存储结构，包括邻接表相关数组、距离数组（表示每个小朋友最少能得到的糖果数）、队列数组、记录每个节点入队次数的数组以及节点是否在队列中的标记数组。
2. 编写添加边的函数，用于构建邻接表。
3. 实现SPFA算法，通过不断更新节点距离，判断图中是否存在负权回路（即某个节点入队次数达到节点总数 (n + 1)，这里加 (1) 是因为引入了超级源点）。
4. 在 main 函数中：
- 读取小朋友的数量 (n) 和要求的数量 (m)。
- 初始化邻接表，根据小朋友之间的要求添加边（不同的 (x) 值对应不同的边权和方向）。
- 建立超级源点与所有小朋友节点的边，边权为 (1)，表示每个小朋友至少有 (1) 颗糖果。
- 调用SPFA算法判断图中是否存在负权回路，如果存在则输出 (-1)（表示无解）。
- 如果不存在负权回路，则将每个小朋友最少能得到的糖果数（存储在 dist 数组中）相加，输出结果。

三、代码逐段分析

（一）头文件和全局变量

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

using namespace std;

typedef long long LL;

const int N = 100010, M = 300010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
LL dist[N];
int q[N], cnt[N];
bool st[N];

1. 头文件：
   • #include <cstdio>：用于标准输入输出函数，如 scanf 和 printf。
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 类型定义：
   • typedef long long LL;：将 long long 类型重命名为 LL，方便后续使用。
3. 常量定义：
   • const int N = 100010, M = 300010;：定义小朋友数量的最大值和边数量的最大值。
4. 变量定义：
   • int n, m;：分别表示小朋友的数量和要求的数量。
   • int h[N], e[M], w[M], ne[M], idx;：邻接表相关数组，h[N] 存储每个节点的头指针，e[M] 存储边的终点，w[M] 存储边权，ne[M] 存储下一条边的指针，idx 用于边的编号。
   • LL dist[N];：记录从超级源点到每个小朋友节点的距离，即每个小朋友最少能得到的糖果数。
   • int q[N], cnt[N];：q[N] 是队列数组，用于SPFA算法；cnt[N] 记录每个节点入队的次数。
   • bool st[N];：标记每个节点是否在队列中。

（二）添加边函数

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

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

（三）SPFA算法函数

bool spfa()
{
    int hh = 0, tt = 1;
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    q[0] = 0;
    st[0] = true;

    while (hh != tt)
    {
        int t = q[ -- tt];
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n + 1) return false;
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    st[j] = true;
                }
            }
        }
    }

    return true;
}

1. 初始化：
   • int hh = 0, tt = 1;：初始化队列的头指针 hh 和尾指针 tt。
   • memset(dist, -0x3f, sizeof dist);：将距离数组初始化为一个极小值，表示未确定每个小朋友最少能得到的糖果数。
   • dist[0] = 0;：超级源点到自身的距离为 (0)。
   • q[0] = 0;：将超级源点入队。
   • st[0] = true;：标记超级源点在队列中。
2. 队列处理：
   • 当队列不为空时，取出队尾节点 t，标记为不在队列中。
   • 遍历节点 t 的所有邻接边，如果通过节点 t 到邻接节点 j 的距离更短，则更新距离 dist[j]，入队次数 cnt[j] 加1。
   • 如果某个节点的入队次数 cnt[j] 达到 (n + 1)，说明存在负权回路，返回 false。
   • 如果邻接节点 j 不在队列中，则将其入队并标记为在队列中。
3. 返回结果：
   • 遍历完所有边后，若没有发现负权回路，返回 true。

（四）main 函数

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int x, a, b;
        scanf("%d%d%d", &x, &a, &b);
        if (x == 1) add(b, a, 0), add(a, b, 0);
        else if (x == 2) add(a, b, 1);
        else if (x == 3) add(b, a, 0);
        else if (x == 4) add(b, a, 1);
        else add(a, b, 0);
    }

    for (int i = 1; i <= n; i ++ ) add(0, i, 1);

    if (!spfa()) puts("-1");
    else
    {
        LL res = 0;
        for (int i = 1; i <= n; i ++ ) res += dist[i];
        printf("%lld\n", res);
    }

    return 0;
}

1. 读取数据并初始化：
   • scanf("%d%d", &n, &m);：读取小朋友的数量 n 和要求的数量 m。
   • memset(h, -1, sizeof h);：初始化邻接表头指针数组为 (-1)。
   • 通过循环读取每个要求（x，a，b），根据 x 的值添加不同的边。
2. 建立超级源点的边：
   • 通过循环建立超级源点（编号为 (0)）与所有小朋友节点（编号从 (1) 到 (n)）的边，边权为 (1)。
3. 判断并计算结果：
   • 调用SPFA算法判断图中是否存在负权回路，如果存在则输出 (-1)。
   • 如果不存在负权回路，则将每个小朋友最少能得到的糖果数（存储在 dist 数组中）相加，得到结果 res，并输出。
4. 结束程序：
   • return 0;：程序正常结束。

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

（一）时间复杂度

1. 输入和建图：读取要求并构建邻接表，时间复杂度为 (O(m))，其中 (m) 是要求的数量。
2. SPFA算法：在最坏情况下，每个节点都可能入队 (n + 1) 次，每次入队处理其邻接边，时间复杂度为 (O((n + 1)m))。但在实际情况中，SPFA算法通常比这个复杂度要快。
   总体时间复杂度为 (O((n + 1)m + m)=O((n + 1)m))，主要由SPFA算法的时间复杂度决定。

（二）空间复杂度

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

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