1 问题

我们知道带权无向图上有一个经典问题：最小生成树。那么如果换成带权有向图呢？

对于一个带权有向图，从中选出一个子图，使得该子图中无环，且存在一个点可以到达其他所有点，则这个子图就是一个树形图。而求出所有树形图中选出边权和最小的一种选法，就是最小树形图问题。

容易想到，解决最小生成树的两种方法都是基于无向成立的，因此不能套用到该问题上。我们就需要一种新的算法。

2 朱刘算法

2.1 算法流程

我们先考虑给定最小树形图的根 \(rt\) 的解法。

我们先考虑一个较简单的问题：求出一个 DAG 的最小树形图。那么显然我们只需要选出所有点的入边中最小的一条即可。

假如我们对任意图进行上述操作，会发现一个问题：我们最后选出的子图很可能带环。那么此时环上一定会有一个点，它的真正入边不再是环上对应的那条入边，而是环外指向他的一条边。而此时假设原先的入边是 \(w\)，新的入边是 \(v\)，那么相当于是对我们最初的答案加上了 \(v-w\)。

那么我们可以这样来做：我们对于每一个点先找出他们的最小入边并相连。接下来考虑每一个点，如果它指向的节点是一个环上的节点，设这条边边权为 \(v\)，指向的点在环上的对应入边权值为 \(w\)，则将这条边的权值改为 \(v-w\)。同时将所有环缩点。重复执行上述过程，直到转化为一个 DAG 上的问题即可。

那么显然经过这样的操作，我们选出来的价值一定和最小树形图是等价的。

现在只需要考虑一个问题，即如何找环。Tarjan 实际上有些复杂，我们有更简单的做法。

2.1.1 找环

令 \(pre_x\) 表示当前 \(x\) 的最小入边对应的另一个节点，\(id_x\) 表示当前节点在图上的最晚前驱（可以用 \(pre\) 跳过来的点）（类似于并查集路径压缩，也类似于 Tarjan 中的 \(low\)），\(bel_x\) 表示 \(x\) 属于哪个环（不属于环 \(bel_x=0\)）。

我们遍历每一个节点 \(x\)，然后沿着 \(pre\) 跳，并沿途更新 \(id_x\)。接下来我们分类讨论：

• 如果走到了 \(rt\)，那么它一定不在环上。
• 如果走到了一个点 \(v\) 的 \(id_v=x\)，则说明一定出现了环。此时还要继续讨论：
  • 如果 \(bel_v=0\)，则说明这是一个新环，遍历环上节点更新 \(bel\) 即可。
  • 否则说明这个环已经被更新过了，一个节点不可能同时是两个环的节点，所以不必操作。
• 如果走到了一个在环上的点，和上面一样的道理，我们不必操作。

这样就可以找到环并将它们缩点了。具体代码如下：

for(int i = 1; i <= n; i++) {
    int x = i;
    while(id[x] != i && bel[x] == -1 && x != rt) {//没有走到根，没有走到环上点，没有走到前驱是自己的点
        id[x] = i;//沿途更新
        x = pre[x];
    }
    if(x != rt && bel[x] == -1) {//找到新环
        bel[x] = ++cnt;//更新 bel
        for(int j = pre[x]; j != x; j = pre[j]) bel[j] = cnt;
    }
}

有了这个关键的技术，剩下的部分就不难完成了。

上面我们探讨的都是给定根的情况，如果不指定根呢？很简单，我们新建超级源点，向所有点连一条 \(\infty\) 的边。这样如果有解，这样的边一定只会选一条，减掉即可；而如果无解，则这样的边会选多条，判断即可。

2.2 完整代码

模板题：【模板】最小树形图。代码如下：

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Maxn = 2e5 + 5;
const int Inf = 1e13;

int n, m, rt;
struct node {
	int u, v, w;
}e[Maxn];

int cnt, bel[Maxn], pre[Maxn], mn[Maxn], id[Maxn];

int Chu_Liu() {
	int ans = 0;
	while(1) {
		for(int i = 1; i <= n; i++) mn[i] = Inf, pre[i] = 0;
		for(int i = 1; i <= m; i++) {//找最小入边
			if(e[i].u != e[i].v && e[i].w < mn[e[i].v]) {
				mn[e[i].v] = e[i].w;
				pre[e[i].v] = e[i].u;
			}
		}
		for(int i = 1; i <= n; i++) if(i != rt && mn[i] == Inf) return -1;
        //如果有点没有最小入边，则一定不可能联通
		for(int i = 1; i <= n; i++) id[i] = bel[i] = -1;
		cnt = 0;
		mn[rt] = 0;
		for(int i = 1; i <= n; i++) {//找环
			int x = i;
			ans += mn[i];//直接求和
			while(id[x] != i && bel[x] == -1 && x != rt) {
				id[x] = i;
				x = pre[x];
			}
			if(x != rt && bel[x] == -1) {
				bel[x] = ++cnt;
				for(int j = pre[x]; j != x; j = pre[j]) bel[j] = cnt;
			}
		}
		if(cnt == 0) break;
		for(int i = 1; i <= n; i++) if(bel[i] == -1) bel[i] = ++cnt;
		for(int i = 1; i <= m; i++) {//重建边
			int tmp = e[i].v;
			e[i].u = bel[e[i].u];
			e[i].v = bel[e[i].v];
			if(e[i].u != e[i].v) e[i].w -= mn[tmp];//修改边权
		} 
		n = cnt;
		rt = bel[rt];
	}
	return ans;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> rt;
	for(int i = 1; i <= m; i++) {
		cin >> e[i].u >> e[i].v >> e[i].w;
	}
	cout << Chu_Liu();
	return 0;
}