秘密的牛奶运输

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2181 字
树上DFS求路径最大次大边，枚举非树边替换
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1490
// 题意：N 点 M 边无向图（可能有重边），求严格次小生成树的边权和，即边权和大于最小生成树的最小生成树。
// 思路：Kruskal 求最小生成树并记录非树边，以每个点为根在树上 DFS 求出到各点路径的最大边与次大边，枚举非树边做替换取最小增量。
// 复杂度：O(N^2+M) 时间 / O(N^2) 空间
// 易错点：非树边权等于路径最大边时必须替换严格次大边，否则算出来的还是最小生成树本身；次大边要按「可重复的第二大」维护。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const int MAXM = 10005;
const long long INF = (1LL << 60);
struct Edge{
    int u, v;
    long long w;
    bool used;
};
Edge e[MAXM];
int fa[MAXN];
vector<pair<int, long long>> adj[MAXN];
long long mx1[MAXN][MAXN];
long long mx2[MAXN][MAXN];
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void dfs(int u, int p, long long a1, long long a2, int s){
    mx1[s][u] = a1;
    mx2[s][u] = a2;
    for(size_t i = 0; i < adj[u].size(); i++){
        int v = adj[u][i].first;
        long long w = adj[u][i].second;
        if(v == p) continue;
        long long n1 = a1;
        long long n2 = a2;
        if(w > a1){
            n1 = w;
            n2 = a1;
        }
        else if(w > a2){
            n2 = w;
        }
        dfs(v, u, n1, n2, s);
    }
}
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    for(int i = 0; i < m; i++){
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].used = false;
    }
    sort(e, e + m, [](const Edge &a, const Edge &b){
        return a.w < b.w;
    });
    for(int i = 1; i <= n; i++) fa[i] = i;
    long long sum = 0;
    for(int i = 0; i < m; i++){
        int a = find(e[i].u);
        int b = find(e[i].v);
        if(a == b) continue;
        fa[a] = b;
        e[i].used = true;
        sum += e[i].w;
        adj[e[i].u].push_back({e[i].v, e[i].w});
        adj[e[i].v].push_back({e[i].u, e[i].w});
    }
    for(int s = 1; s <= n; s++) dfs(s, 0, -1, -1, s);
    long long ans = INF;
    for(int i = 0; i < m; i++){
        if(e[i].used) continue;
        int u = e[i].u;
        int v = e[i].v;
        long long w = e[i].w;
        if(w > mx1[u][v]){
            ans = min(ans, sum - mx1[u][v] + w);
        }
        else if(mx2[u][v] >= 0 && w > mx2[u][v]){
            ans = min(ans, sum - mx2[u][v] + w);
        }
    }
    cout << ans << '\n';
    return 0;
}
秘密的牛奶运输

正文

一本通·提高篇的其它内容
