秘密的牛奶运输

次小生成树 T4 Kruscal扩展 并查集 DFS 信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn) Farmer John 要把他的牛奶运输到各个销售点。运输过程中，可以先把牛奶运输到一些销售点，再由这些销售点分别运输到其他销售点。 运输的总距离越小，运输的成本也就越低。低成本的运输是 Farmer John 所希望的。不过，他并不想让他的竞争对手知道他具体的运输方案，所以他希望采用费用第二小的运输方案而不是最小的。现在请你帮忙找到该运输方案。

输入

第一行是两个整数 $N,M$，表示顶点数和边数；

接下来 $M$ 行每行 $3$ 个整数，$x,y,z$，表示一条路的两端 $x,y$ 和距离 $z$。

输出

仅一行，输出第二小方案。

输入样例

4 4
1 2 100
2 4 200
2 3 250
3 4 100

输出样例

450

数据范围

对于全部数据，$1\le N\le 2000,1\le M\le 20000,1\le z\le 10^9$​​ ，数据可能有重边。

思路

求出无向图中的次小生成树。

次小生成树的定义：给一个带权的图, 把图中的所有生成树按权值从小到大排序, 第二小的就是次小生成树。 通常有两种方法求：

1. 先求最小生成树, 再枚举删去最小生成树中的边求一次最小生成树, 时间复杂度为 $O(m\log m+nm)$ , $nm$是对每条边求最小生成树, 因为已经排过序, 故为$m$。
2. 先求最小生成树, 然后依次枚举非树边, 然后将该边加入树中, 同时从树中去掉一条边, 使得最终的图仍是一棵树。这么做下去一定可以求出次小生成树。

次小生成树又分为两种情况, 一种是非严格最小生成树, 可以与之前的权值相同。另一种是严格最小生成树, 必须权值比之前的生成树小才行。

可以发现, 方法1无法保证可以求得严格最小生成树, 有可能枚举完得到的都是非严格最小生成树。而方法2则可以稳定得出严格和非严格的。因此以下主要介绍方法2。

方法2中去边并不一定非要枚举所有能去的边, 设原本权值和为 $sum$, 经过操作后得到： $sum+W_{新}-W_{旧}$ , 要让整个最小, 其中 $W_{新}$ 根据权值从小到大选, 已经是当前能选的最小值, 故可以让 $W_{旧}$ 最大。因此可以求出一个数组$dist[a][b]$记录在最小生成树中, $a,b$之间的最大边权。有很多种求法, 不过这里可以用最简单的DFS。

故总时间复杂度为$O(m+n^2+m\log m)$ 。若用LCA优化可以到 $O(m\log n)$ 。

设T为图G的一颗生成树, 对于非树边a和树边b, 插入边a, 并删除边b的操作为 (+a, -b)。 若T+a-b之后, 依然是一棵生成树, 称(+a,-b)是T的一个可行交换。 称由T进行一次可行变换所得到的新的生成树集合称为T的临集。 定理：严格/非严格次小生成树一定在该临集中。—算法一本通

代码流程为：

1. 求最小生成树, 对于每条边标记是树边还是非树边, 并建立最小生成树图。
2. DFS预处理任意两点间的边权最大值dist
3. 依次枚举所有非树边, 求$min(sum+w-dist[a][b])$, 满足 $w>dist[a][b]$ 。

而求严格次小生成树时, 需要再维护一个任意两点间的边权次大值。因为去掉的 $dist[a][b]$ 有可能会和 $w$ 相等, 这样就不是严格最小生成树。但也不能直接跳过, 可以选择次大值, 且次大值和最大值不能显得更。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 2e3 + 10, M = 2e4 + 10;
typedef long long LL;
int f[N];
int n, m;
struct Edge
{
    int a, b, c;
    bool flag;
    bool operator<(const Edge &W) const
    {
        return c < W.c;
    }
} e[M];
int h[N], ne[N * N], E[N * N], w[N * N], idx;
int dist[N][N];
 
int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
void add(int a, int b, int c) { E[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
 
void dfs(int u, int fa, int maxd, int d[])
{
    d[u] = maxd;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = E[i];
        if (j == fa)
            continue;
 
        dfs(j, u, max(maxd, w[i]), d);
    }
}
 
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++)
        f[i] = i;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[i] = {a, b, c};
    }
    LL sum = 0;
    sort(e, e + m);
    for (int i = 0; i < m; i++)
    {
        int a = e[i].a, b = e[i].b, c = e[i].c;
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            f[pb] = pa;
            e[i].flag = true;
            add(a, b, c), add(b, a, c);
            sum += c;
        }
    }
    for (int i = 1; i <= n; i++)
        dfs(i, 0, 0, dist[i]);
 
    LL res = 1e18;
    for (int i = 0; i < m; i++)
    {
        if (e[i].flag)
            continue;
        int a = e[i].a, b = e[i].b, c = e[i].c;
        if (c > dist[a][b])
            res = min(sum + c - dist[a][b], res);
    }
 
    cout << res << endl;
    return 0;
}