AcWing 1148 秘密的牛奶运输

题目传送门

一、次小生成树

蓝色边为新添加的边，黑色边为最小生成树

如图所示，我们求出了图的一个最小生成树(最小生成树不唯一噢~)，然后尝试连接\(u\)到\(v\)，从而在生成树中\(u\)到\(v\)的路径加上\(u\)到\(v\)的这条边就构成了一个环，此时删掉生成树中\(u\)到\(v\)的路径中的任意一条边，就生成新的生成树了。

由最小生成树的性质知道，\(u,v\)之间的边权一定是这个环上边权最大的一个了，否则就不是最小生成树了，为了生成一棵次小生成树，需要在环中删除\(u\sim v\)路径中边权的最大值。

设原最小生成树的边权之和为sum(这个在\(Kruskal\)算法求最小生成树过程中可以计算出)，\(u,v\)的边权为w，待删除的树边的边权是d，则新的生成树边权之和为sum + w - d，sum和d是固定的，为了边权之和尽可能的小，则待删去的边权\(d\)要尽可能的大。

因为题目要求的是严格意义上的次小生成树，要求新生成树的权值和一定要比最小生成树大，所以在上图的环中如果删除了和w一样大的树边，得到的还是最小生成树（最小生成树不唯一）!

既然确定生成树中\(u\)到\(v\)路径中边的边权都不大于\(w\)，那么只好求出\(u\)到\(v\)的路径中边权的最大值和次大值了，即使最大值等于w，次大值也会小于w。下面的问题就是如何在一棵树中求任意两个节点间路径中最大的边权和次大的边权了，显然可以用\(dfs\)遍历来实现。

二、实现代码

#include 
using namespace std;
typedef long long LL;
const int N = 510, M = 10010;

int n, m;
//结构体
struct Edge {
    int a, b, w;
    bool flag; //是不是最小生成树中的边
    bool operator<(const Edge &t) const {
        return w < t.w;
    }
} edge[M];

int dist1[N][N]; //从i出发，到达j最短距离
int dist2[N][N]; //从i出发，到达j次短距离
LL sum;          //最小生成树的边权和
//邻接表
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
//并查集
int p[N];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return 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]) { //枚举u的每一条出边
        int j = e[i];                   // j为u的对边节点
        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]; //更新次大值
            // d1,d2继续传递，是为了记录结果到数组dist1,dist2中，引用传递
            dfs(j, u, td1, td2, d1, d2);
        }
    }
}

int main() {
    cin >> n >> m;
    //初始化邻接表
    memset(h, -1, sizeof h);

    // Kruskal建图
    for (int i = 0; i < m; i++)
        cin >> edge[i].a >> edge[i].b >> edge[i].w;
    sort(edge, edge + m);

    //并查集初始化
    for (int i = 1; i <= n; i++) p[i] = i;

    //最小生成树
    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].flag = true;
        }
    }

    // dist1[i][j]和dist2[i][j]
    //计算i节点到最小生成树中j节点路径中的最长和次长距离是多少
    for (int i = 1; i <= n; i++)
        dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]);

    LL res = 1e18;              //预求最小值，先设最大值
    //枚举所有不在最小生成树中的边,尝试加入u~v的这条直边
    for (int i = 0; i < m; i++)
        if (!edge[i].flag) {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            LL t;
            /*
            1、直边 大于 最大边
               替换掉最大边

            2、直边 等于 最大边
               判断是不是大于次大边，如果是，替换次大边

            3、直边 小于 最大边
            这是不可能的，随便在最小生成树外找一条边就可以替换掉原来的边，
            那还是啥最小生成树?
            */
            if (w > dist1[a][b])
                t = sum + w - dist1[a][b];                //删除最大边
            else if (w == dist1[a][b] && w > dist2[a][b]) //删除次大边
                t = sum + w - dist2[a][b];

            //次小生成树的边权和
            res = min(res, t);
        }
    //输出
    printf("%lld\n", res);
    return 0;
}