题解：秘密的牛奶运输问题

一、题目背景

农夫约翰要将牛奶运输到各个销售点，运输总距离越小成本越低。但他不想让竞争对手知道运输方案，所以希望采用费用第二小的运输方案（要求严格大于最小费用方案），给定销售点数 (N) 和交通线路数 (M)，以及各线路的连接点和距离，需要找出第二小费用的运输方案。

二、解题思路

本题通过计算最小生成树，在此基础上找出第二小的生成树费用。具体步骤如下：
1. 定义结构体存储边的信息，包括边的两个端点、边权以及是否在最小生成树中。同时定义并查集数组、邻接表数组、两个距离数组（分别记录从每个点出发到其他点路径上的最大边权和次大边权）。
2. 读取销售点数 (n) 和交通线路数 (m)，以及每条线路的信息（两个端点和距离），存储到边数组中。
3. 对边按照边权从小到大排序，初始化并查集。
4. 使用Kruskal算法构建最小生成树，记录最小生成树的总费用 (sum)，将最小生成树的边标记并加入邻接表。
5. 对最小生成树的每个节点进行深度优先搜索（DFS），计算从每个节点出发到其他节点路径上的最大边权 (dist1) 和次大边权 (dist2)。
6. 遍历所有不在最小生成树中的边，尝试将其加入最小生成树，计算替换后的总费用 (t)（即 (sum + 该边权 - 原路径上的最大或次大边权)），更新第二小费用 (res)。
7. 输出第二小费用 (res)。

三、代码逐段分析

（一）头文件和全局变量

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

using namespace std;

typedef long long LL;

const int N = 510, M = 10010;

int n, m;
struct Edge
{
    int a, b, w;
    bool f;
    bool operator< (const Edge &t) const
    {
        return w < t.w;
    }
}edge[M];
int p[N];
int dist1[N][N], dist2[N][N];
int h[N], e[N * 2], w[N * 2], ne[N * 2], idx;

1. 头文件：
   • #include <cstdio>：用于标准输入输出函数，如 scanf 和 printf。
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数，如 sort 用于排序。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 类型定义：
   • typedef long long LL;：将 long long 类型重命名为 LL，方便后续使用。
3. 常量定义：
   • const int N = 510, M = 10010;：定义销售点的最大数量和交通线路的最大数量。
4. 变量定义：
   • int n, m;：分别表示销售点数和交通线路数。
   • struct Edge：定义结构体存储边的信息，包括两个端点 a、b，边权 w，以及是否在最小生成树中的标记 f，并重载 < 运算符用于边按边权排序。
   • edge[M];：数组 edge 用于存储所有边的信息。
   • int p[N];：并查集数组，用于判断两个点是否在同一连通分量中。
   • int dist1[N][N], dist2[N][N];：二维数组，分别记录从每个点出发到其他点路径上的最大边权和次大边权。
   • int h[N], e[N * 2], w[N * 2], ne[N * 2], idx;：邻接表相关数组，h[N] 存储每个点的头指针，e[N * 2] 存储边的终点，w[N * 2] 存储边权，ne[N * 2] 存储下一条边的指针，idx 用于边的编号。

（二）邻接表添加边函数

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

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

（三）并查集查找函数

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

该函数用于在并查集中查找节点 x 的根节点，同时进行路径压缩，提高后续查找效率。如果 p[x] 不等于 x，则递归查找根节点并更新 p[x] 为根节点，最后返回根节点。

（四）深度优先搜索函数

void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[])
{
    d1[u] = maxd1, d2[u] = maxd2;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != fa)
        {
            int td1 = maxd1, td2 = maxd2;
            if (w[i] > td1) td2 = td1, td1 = w[i];
            else if (w[i] < td1 && w[i] > td2) td2 = w[i];
            dfs(j, u, td1, td2, d1, d2);
        }
    }
}

该函数用于深度优先搜索，从节点 u 出发，参数 fa 为父节点，maxd1 和 maxd2 分别为当前路径上的最大边权和次大边权，d1[] 和 d2[] 分别为记录最大边权和次大边权的数组。
1. 首先将当前节点 u 的最大边权和次大边权分别设为 maxd1 和 maxd2。
2. 然后遍历当前节点的所有邻接边，如果邻接节点 j 不是父节点 fa，则根据边权 w[i] 更新 td1 和 td2（最大边权和次大边权）。
3. 最后递归调用 dfs 函数，继续搜索邻接节点。

（五）main 函数

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edge[i] = {a, b, w};
    }

    sort(edge, edge + m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    LL sum = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            p[pa] = pb;
            sum += w;
            add(a, b, w), add(b, a, w);
            edge[i].f = true;
        }
    }

    for (int i = 1; i <= n; i ++ ) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]);

    LL res = 1e18;
    for (int i = 0; i < m; i ++ )
        if (!edge[i].f)
        {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            LL t;
            if (w > dist1[a][b])
                t = sum + w - dist1[a][b];
            else if (w > dist2[a][b])
                t = sum + w - dist2[a][b];
            res = min(res, t);
        }

    printf("%lld\n", res);

    return 0;
}

1. 输入数据并初始化：
   • scanf("%d%d", &n, &m);：读取销售点数 n 和交通线路数 m。
   • memset(h, -1, sizeof h);：初始化邻接表头指针数组 h 为 -1，表示没有边。
   • 通过循环读取每条线路的信息（两个端点和距离），存储到边数组 edge 中。
   • sort(edge, edge + m);：对边按照边权从小到大排序。
   • for (int i = 1; i <= n; i ++ ) p[i] = i;：初始化并查集，每个点的父节点为自身。
2. 构建最小生成树：
   • LL sum = 0;：初始化最小生成树的总费用为 0。
   • 通过循环遍历边数组，利用并查集判断两个端点是否在同一连通分量中，如果不在，则将其加入最小生成树，更新总费用 sum，将边加入邻接表，并标记该边在最小生成树中（edge[i].f = true;）。
3. 深度优先搜索计算距离数组：
   • 通过循环对最小生成树的每个节点进行深度优先搜索，计算从每个节点出发到其他节点路径上的最大边权 dist1 和次大边权 dist2。
4. 寻找第二小生成树费用：
   • LL res = 1e18;：初始化第二小费用为一个很大的值。
   • 循环遍历所有不在最小生成树中的边，尝试将其加入最小生成树，根据该边权与 dist1[a][b] 和 dist2[a][b] 的比较，计算替换后的总费用 t，更新第二小费用 res。
5. 输出结果并结束程序：
   • printf("%lld\n", res);：输出第二小费用。
   • return 0;：程序正常结束。

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

（一）时间复杂度

1. 输入和初始化：读取边信息和初始化并查集等操作，时间复杂度为 (O(m))，其中 (m) 是交通线路数。
2. 边排序：对 (m) 条边进行排序，时间复杂度为 (O(m \log m))。
3. 构建最小生成树：Kruskal算法构建最小生成树，时间复杂度为 (O(m \log n))，其中 (n) 是销售点数。
4. 深度优先搜索：对每个节点进行深度优先搜索，时间复杂度为 (O(n + m))。
5. 寻找第二小生成树费用：遍历不在最小生成树中的边，时间复杂度为 (O(m))。
   总体时间复杂度为 (O(m \log m + m \log n + n + m + m)=O(m \log m + m \log n + n))，主要由边排序和构建最小生成树的时间复杂度决定。

（二）空间复杂度

1. 存储边信息：边数组 edge[M] 占用空间为 (O(m))。
2. 并查集数组：p[N] 占用空间为 (O(n))。
3. 距离数组：dist1[N][N] 和 dist2[N][N] 占用空间为 (O(n^2))。
4. 邻接表数组：h[N]、e[N * 2]、w[N * 2]、ne[N * 2] 占用空间为 (O(m))。
   总体空间复杂度为 (O(m + n + n^2 + m)=O(n^2 + m))，主要由距离数组和边信息存储的空间占用决定。

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