题解：排队布局问题

一、题目背景

农夫约翰有 (N) 头编号从 (1) 到 (N) 的奶牛，沿直线排队等候喂食。一些奶牛之间有好感，希望彼此距离不超过给定数 (L)；另一些奶牛相互反感，希望彼此距离不小于给定数 (D) 。需要根据这些条件，判断是否存在满足要求的排队方案，若存在，计算 (1) 号奶牛和 (N) 号奶牛间可能的最大距离。

二、解题思路

本题可通过构建差分约束系统，利用SPFA算法求解。将每头奶牛看作图中的一个节点，根据奶牛之间的好感和反感关系以及奶牛排队的顺序关系构建有向边，通过SPFA算法判断是否存在负权回路（表示不存在满足要求的方案），并计算 (1) 号奶牛和 (N) 号奶牛间的最大距离。

具体步骤如下：
1. 定义图的存储结构，包括邻接表相关数组、距离数组（记录奶牛之间的距离）、队列数组、记录每个节点入队次数的数组以及节点是否在队列中的标记数组。
2. 编写添加边的函数，用于构建邻接表。
3. 实现SPFA算法，通过不断更新节点距离，判断图中是否存在负权回路，并在无负权回路时计算最短距离。
4. 在 main 函数中：
- 读取奶牛的数量 (n)、表示好感关系的数量 (m1) 和表示反感关系的数量 (m2)。
- 初始化邻接表，根据奶牛排队顺序构建从 (i + 1) 到 (i) 的边，边权为 (0)（表示距离非负且 (i) 号奶牛与 (i + 1) 号奶牛距离可以为 (0)）。
- 读取好感关系，构建从奶牛 (a) 到奶牛 (b) 的边，边权为 (c)（表示 (a) 和 (b) 至多相隔 (c) 的距离）。
- 读取反感关系，构建从奶牛 (b) 到奶牛 (a) 的边，边权为 (-c)（表示 (a) 和 (b) 至少相隔 (c) 的距离）。
- 调用SPFA算法判断是否存在负权回路，若存在则输出 (-1)（表示不存在满足要求的方案）。
- 若不存在负权回路，再次调用SPFA算法（只将 (1) 号节点入队），若 (1) 号奶牛和 (N) 号奶牛间的距离为初始的无穷大值，则输出 (-2)（表示距离可以任意大）；否则输出该距离值。

三、代码逐段分析

（一）头文件和全局变量

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

using namespace std;

const int N = 1010, M = 10000 + 10000 + 1000 + 10, INF = 0x3f3f3f3f;

int n, m1, m2;
int h[N], e[M], w[M], ne[M], idx;
int 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. 常量定义：
   • const int N = 1010, M = 10000 + 10000 + 1000 + 10, INF = 0x3f3f3f3f;：定义节点的最大数量（奶牛数量）、边的最大数量以及表示无穷大的常量。
3. 变量定义：
   • int n, m1, m2;：分别表示奶牛的数量、好感关系的数量和反感关系的数量。
   • int h[N], e[M], w[M], ne[M], idx;：邻接表相关数组，h[N] 存储每个节点的头指针，e[M] 存储边的终点，w[M] 存储边权，ne[M] 存储下一条边的指针，idx 用于边的编号。
   • int 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 size)
{
    int hh = 0, tt = 0;
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);

    for (int i = 1; i <= size; i ++ )
    {
        q[tt ++ ] = i;
        dist[i] = 0;
        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] + w[i])
            {
                dist[j] = dist[t] + w[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. 初始化：
   • int hh = 0, tt = 0;：初始化队列的头指针 hh 和尾指针 tt。
   • memset(dist, 0x3f, sizeof dist);：将距离数组初始化为无穷大值，表示未确定奶牛之间的距离。
   • memset(st, 0, sizeof st);：将节点在队列中的标记初始化为 false。
   • memset(cnt, 0, sizeof cnt);：将每个节点的入队次数初始化为0。
   • 根据传入的 size，将相应范围内的节点入队，设置距离为 (0)，标记为在队列中。
2. 队列处理：
   • 当队列不为空时，取出队头节点 t，标记为不在队列中。
   • 遍历节点 t 的所有邻接边，如果通过节点 t 到邻接节点 j 的距离更短，则更新距离 dist[j]，入队次数 cnt[j] 加1。
   • 如果某个节点的入队次数 cnt[j] 达到节点总数 n，说明存在负权回路，返回 true。
   • 如果邻接节点 j 不在队列中，则将其入队并标记为在队列中。
3. 返回结果：
   • 遍历完所有边后，若没有发现负权回路，返回 false。

（四）main 函数

int main()
{
    scanf("%d%d%d", &n, &m1, &m2);
    memset(h, -1, sizeof h);

    for (int i = 1; i < n; i ++ ) add(i + 1, i, 0);
    while (m1 -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a > b) swap(a, b);
        add(a, b, c);
    }
    while (m2 -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a > b) swap(a, b);
        add(b, a, -c);
    }

    if (spfa(n)) puts("-1");
    else
    {
        spfa(1);
        if (dist[n] == INF) puts("-2");
        else printf("%d\n", dist[n]);
    }

    return 0;
}

1. 读取数据并初始化：
   • scanf("%d%d%d", &n, &m1, &m2);：读取奶牛的数量 n、好感关系的数量 m1 和反感关系的数量 m2。
   • memset(h, -1, sizeof h);：初始化邻接表头指针数组为 (-1)。
   • 通过循环构建奶牛排队顺序相关的边，从 (i + 1) 到 (i) 的边权为 (0)。
2. 构建好感和反感关系边：
   • 通过循环读取好感关系，构建从奶牛 a 到奶牛 b 的边，边权为 c，若 a > b 则交换 a 和 b。
   • 通过循环读取反感关系，构建从奶牛 b 到奶牛 a 的边，边权为 (-c，若a > b则交换a和b`。
3. 判断并计算结果：
   • 调用SPFA算法（传入 n）判断是否存在负权回路，若存在则输出 (-1`。
   • 若不存在负权回路，再次调用SPFA算法（传入 1，只将 (1) 号节点入队），若 (1) 号奶牛和 (N) 号奶牛间的距离为初始的无穷大值，则输出 (-2`；否则输出该距离值。
4. 结束程序：
   • return 0;：程序正常结束。

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

（一）时间复杂度

1. 输入和建图：读取关系并构建邻接表，时间复杂度为 (O(m1 + m2))，其中 (m1) 和 (m2) 分别是好感和反感关系的数量。
2. SPFA算法：在最坏情况下，每个节点都可能入队 (n) 次，每次入队处理其邻接边，时间复杂度为 (O(nm))，其中 (m = m1 + m2 + n - 1) 是边的总数。这里两次调用SPFA算法，一次判断负权回路，一次计算距离，所以总体时间复杂度为 (O(nm))。
   总体时间复杂度为 (O(n(m1 + m2 + n - 1)))。

（二）空间复杂度

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

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