最小树形图-朱刘算法学习笔记

GIFBMP · 2022-12-30 20:29:17 · 个人记录

首先我们对于一个有向图，先把除了根之外每个点边权最小的前驱加入答案，但是此时可能成环，于是我们对于一个环上的点 x，设 c_x 表示环中连向 x 的边权，那么对于 x 没被选中的前驱，设它的边权为 w，那么它的边权应变为 w-c_x，重复这一过程，直到图被缩成一个点，算法结束。

缩点过程用并查集实现即可。

Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
const int MAXN = 1e4 + 10 , INF = 0x3f3f3f3f ;
typedef long long ll ;
int n , m , rt , mn[MAXN] , p[MAXN] , fa[MAXN] , tot , vis[MAXN] ;
ll ans ;
struct edge {
    int u , v , w ;
    edge (int u = 0 , int v = 0 , int w = 0) : u(u) , v(v) , w(w) {}
} e[MAXN << 1] ;
int main () {
    scanf ("%d%d%d" , &n , &m , &rt) ;
    for (int i = 1 ; i <= m ; i++)
        scanf ("%d%d%d" , &e[i].u , &e[i].v , &e[i].w) ;
    while (1) {
        for (int i = 1 ; i <= n ; i++) mn[i] = INF , p[i] = fa[i] = vis[i] = 0 ;
        for (int i = 1 ; i <= m ; i++) {
            if (e[i].u == e[i].v) continue ;
            if (e[i].w < mn[e[i].v]) mn[e[i].v] = e[i].w , fa[e[i].v] = e[i].u ;
        }
        mn[rt] = 0 ; tot = 0 ;
        for (int i = 1 ; i <= n ; i++) {
            if (mn[i] == INF) return !printf ("-1") ;
            ans += mn[i] ;
        }
        for (int i = 1 ; i <= n ; i++) {
            int x = i ;
            for (; x != rt && vis[x] != i && !p[x] ; vis[x] = i , x = fa[x]) ;
            if (x != rt && !p[x]) {
                p[x] = ++tot ;
                for (int j = fa[x] ; j != x ; j = fa[j]) p[j] = tot ;
            }
        }
        if (!tot) break ;
        for (int i = 1 ; i <= n ; i++) if (!p[i]) p[i] = ++tot ;
        for (int i = 1 ; i <= m ; i++)
            e[i].w -= mn[e[i].v] , e[i].u = p[e[i].u] , e[i].v = p[e[i].v] ;
        rt = p[rt] ; n = tot ;
    }
    printf ("%lld\n" , ans) ;
    return 0 ;
}