Acwing1148. 秘密的牛奶运输（次小生成树）

Acwing1148. 秘密的牛奶运输（次小生成树） Acwing算法提高课

次小生成树有分严格和非严格

1. 严格：次小树的权值必须比最小树的大
2. 非严格：权值可以相等，只要加的边和删的不是同一条即可

经常用的一种方法是枚举非树边，尝试替代原最小生成树上的某条边。非树边肯定有两端点，要求替代的是这两点之间路径上最大的边。这样才能保证新生成的树比原本大且尽量小。这种方法可以处理严格也可以处理不严格，比较灵活。

同时要注意的是：不仅要记录两点之间路径上最大的边，还要记录两点之间路径上次大的边。当你枚举的这条非树边权值等于最大边时，就可以尝试替代次大边

代码 + 注释：

#include
#include
#include
#define _CRT_SECURE_NO_WARNINGS
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define cout_double(a) cout << setiosflags(ios::fixed) << setprecision(a)
#define sca scanf
#define pri printf
#define ul u << 1
#define ur u << 1 | 1
//#pragma GCC optimize(2)
using namespace std;

typedef long long ll;
typedef pair PII;

const int N = 510, M = 10010;
int INF = 0x3f3f3f3f, mod = 100003;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S;
int p[N], h[N], ne[M], e[M], wf[M], idx;
int dist[N][N], distc[N][N];
struct edge
{
    int a, b, x;
    bool f;
}ed[M];

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

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

bool cmp(edge a, edge b) {
    return a.x < b.x;
}

void dfs(int u, int fa, int maxd, int maxdc, int id) { //求次小生成树的精髓
    //dfs暴搜记录最小生成树上任意两点间的路径中的 最大边权 和 次大边权
    dist[id][u] = maxd;
    distc[id][u] = maxdc;//次
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j != fa) { //防止回搜父节点
            if (maxd > wf[i])maxdc = max(maxdc, wf[i]); 
            //如果最大边权不可替代，尝试更新次大边权
            else if (maxd < wf[i])maxdc = maxd;
            //一旦最大边权可以替代，次大肯定等于原来的最大

            //如果相等显然不需要更新

            dfs(j, u, max(maxd, wf[i]), maxdc, id);
        }
    }
}

int main() {
    cinios;
    
    cin >> n >> m;
    mem(h, -1);
    for (int i = 1; i <= n; i++)p[i] = i;

    for (int i = 0; i < m; i ++ ) {
        int a, b, x;
        cin >> a >> b >> x;
        ed[i] = { a,b,x };
    }

    sort(ed, ed + m, cmp);//贪心

    ll sum = 0;
    for (int i = 0; i < m; i++) { //先标准建一颗最小生成树
        int a = ed[i].a, b = ed[i].b, w = ed[i].x;
        int fa = find(a), fb = find(b);
        if (fa != fb) { 
            sum += w;
            ed[i].f = true;//标记为树上的边
            add(a, b, w), add(b, a, w);
            //建这颗树
            p[fa] = fb;
        }
    }

    for (int i = 1; i <= n; i++)dfs(i, -1, 0, 0, i);
    //因为要求任意两点间信息，所以每个点都暴搜一遍

    ll ans = LNF;
    for (int i = 0; i < m; i++)
        if (!ed[i].f) { //枚举所有非树边
            int a = ed[i].a, b = ed[i].b, w = ed[i].x;

            //一旦一条非树边的权值大于原来树上这两点间路径上的最大边权
            //显然删掉树上{a，b}这条边，加上 w ，这颗生成树的权值肯定增大
            //枚举所有这样的操作，显然可以得到一颗次小生成树

            //但要注意次小生成树有分严格和非严格
            //严格：次小树的权值必须比最小树的大
            //非严格：可以相等，只要加的边和删的不是同一条即可

            if (w > dist[a][b]) //这里要求的是一个严格次小生成树
                ans = min(ans, sum - dist[a][b] + w);
            else if (w == dist[a][b]) //一旦相同可以尝试更新{a，b}路径的次小边
                //如果不存在，distc[a][b] == 0
                ans = min(ans, sum - distc[a][b] + w);

            //可能会有疑问，为什么没有 w < dist[a][b] ?
            //因为如果有，显然 w 应该代替{a，b}路径的最大边，形成一颗更小的生成树
            //跟之前求最小生成树就矛盾了
        }

    cout << ans;

    return 0;
}