秘密的牛奶运输

原题链接

题目描述

农夫约翰要把他的牛奶运输到各个销售点。

运输过程中，可以先把牛奶运输到一些销售点，再由这些销售点分别运输到其他销售点。

运输的总距离越小，运输的成本也就越低。

低成本的运输是农夫约翰所希望的。

不过，他并不想让他的竞争对手知道他具体的运输方案，所以他希望采用费用第二小的运输方案而不是最小的。

现在请你帮忙找到该运输方案。

注意：

• 如果两个方案至少有一条边不同，则我们认为是不同方案；
• 费用第二小的方案在数值上一定要严格大于费用最小的方案；
• 答案保证一定有解；

---

思路 严格次小生成树

根据题意，就是要求严格次小生成树

求出最小生成树后，需要用非树边去替换树边

而对于非树边来说（a,b为非树边的两个端点），如果要用当前边替换进入

可以断了a~b中的其中一条边，然后最小生成树因此变成了两棵树（a->… , …->b->…）

再加上当前的非树边，将两棵树连接在一起

连接后的树的权值一定要最越大越好，生成树的权值=最小生成树权值-删去的树边+添加的非树边

其中删去的树边权值是越大越好，因此呢，是需要求出a到b中最大的权值边，

但是可能存在最大的权值边等于添加的非树边，因此可以用次小边代替

步骤

1. 求出最小生成树，并且存储所有的数边
2. 在深搜枚举每个点到达其他点的第一小边，和第二小边。需要注意的是，第二小边是需要严格大于第一小边的，否则对于最小树边和当前枚举的非树边长度相同时，就不能替换了，但此时却可以替换长度次大的树边。所以第二小边需要严格小于第一小边
3. 枚举每一条非树边，找出替换后的树的最小权值

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 510, M = 10010;

int n, m;
int h[N], e[N << 1], w[N << 1], ne[N << 1], idx;
int dmax1[N][N], dmax2[N][N], p[N];
struct Edge {
    int a, b, w;
    bool isTree;
    bool operator < (const Edge &W) const {
        return w < W.w;
    }
};

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

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

void dfs(int u, int fa, int max1, int max2, int d1[], int d2[]) {
    d1[u] = max1, d2[u] = max2;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        int t1 = max1, t2 = max2;
        if (w[i] > t1) t2 = t1, t1 = w[i];
        else if (w[i] < t1 && w[i] > t2) t2 = w[i];
        dfs(j, u, t1, t2, d1, d2);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(h, -1, sizeof h);

    cin >> n >> m;
    vector<Edge> E(m);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        E[i] = {a, b, w};
    }

    // kruskal
    sort(E.begin(), E.end());
    for (int i = 1; i <= n; i++) p[i] = i;

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

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

    LL res = 1e18;
    for (int i = 0; i < m; i++)
        if (!E[i].isTree) {
            int a = E[i].a, b = E[i].b, w = E[i].w;
            if (w > dmax1[a][b]) res = min(res, sum - dmax1[a][b] + w);
            else if (w > dmax2[a][b]) res = min(res, sum - dmax2[a][b] + w);
        }

    cout << res << endl;

    return 0;
}