最小树形图学习笔记
退役前想学但没时间学的 useless algorithm，退役后找时间都学掉。这是其中之一。
有向图上的最小生成树称为最小树形图（Directed Minimum Spanning Tree）。
本文默认树形图为外向树，即除根以外的所有点的入度为 \(1\)，根的入度为 \(0\)。
最小树形图问题即求一个有向图的以 \(rt\) 节点为根的最小树形图。
1965 年，朱永津和刘振宏提出了最小树形图的朱刘算法。
朱刘算法与无向图的 Boruvka 最小生成树算法有一些异曲同工之处，其算法流程如下：
- 对于每个非根节点，找到其最小入边，记录边权 \(val\) 以及边的起点 \(vtx\)。
- 如果存在一个非根节点不存在入边，返回无解，算法结束。
- 将每个非根节点的入边边权累加进答案。
- 如果无环，返回答案，算法结束。
- 将每个环缩成一个点，删除所有环上的边。对于每条不在环上的边 \((u,v,w)\)，将其边权减去 \(val(v)\)。回到步骤一。
算法对无解的判定和有向无环图的情况是显然正确的。可以证明，当找到一个环时，一定存在一个最小树形图，包含环上除了一条边以外的所有边。算法步骤五中对边权的修改相当于一个反悔的过程，保证了算法的正确性。
显然，算法的每一轮会缩掉至少一个环，使得点数至少减少一。算法每一轮的时间复杂度为 \(O(m)\)，因此总复杂度为 \(O(nm)\)。
模板题：最小树形图、Teen Girl Squad。
代码
// Problem: P4716 【模板】最小树形图
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4716
// Memory Limit: 250 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
template<int mod>
inline unsigned int down(unsigned int x) {
return x >= mod ? x - mod : x;
}
template<int mod>
struct Modint {
unsigned int x;
Modint() = default;
Modint(unsigned int x) : x(x) {}
friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
friend Modint operator/(Modint a, Modint b) {return a * ~b;}
friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
friend Modint operator~(Modint a) {return a ^ (mod - 2);}
friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
friend Modint& operator++(Modint& a) {return a += 1;}
friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
friend Modint& operator--(Modint& a) {return a -= 1;}
friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};
const int N = 105, M = 1e4 + 5, inf = 0x1f1f1f1f;
int n, m, rt, val[N], vtx[N], id[N], vis[N];
struct Edge {
int u, v, w;
Edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
friend istream& operator>>(istream& in, Edge& e) {
return in >> e.u >> e.v >> e.w;
}
friend ostream& operator<<(ostream& out, Edge e) {
return out << e.u << " " << e.v << " " << e.w;
}
}e[M];
int ZhuLiu(int rt) {
int ans = 0;
while(true) {
rep(i, 1, n) {
val[i] = inf;
vtx[i] = id[i] = vis[i] = 0;
}
rep(i, 1, m) {
if(e[i].u != e[i].v && e[i].w < val[e[i].v]) {
val[e[i].v] = e[i].w;
vtx[e[i].v] = e[i].u;
}
}
val[rt] = 0;
rep(i, 1, n) {
if(val[i] == inf) return -1;
ans += val[i];
}
int cnt = 0;
rep(i, 1, n) {
if(i != rt) {
int u = i;
while(u != rt && vis[u] != i && !id[u]) {
vis[u] = i;
u = vtx[u];
}
if(u != rt && !id[u]) {
id[u] = ++cnt;
for(int v = vtx[u]; v != u; v = vtx[v]) id[v] = cnt;
}
}
}
if(!cnt) return ans;
rep(i, 1, n) if(!id[i]) id[i] = ++cnt;
rep(i, 1, m) {
e[i].w -= val[e[i].v];
e[i].u = id[e[i].u];
e[i].v = id[e[i].v];
}
n = cnt;
rt = id[rt];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> rt;
rep(i, 1, m) cin >> e[i];
cout << ZhuLiu(rt) << endl;
return 0;
}
最小树形图有更优秀的 Tarjan 算法，可以做到 \(O(m+n\log n)\) 的复杂度，但我还没学。
如果根没有指定，可以建超级源向每个点连接边权为 \(+\infty\) 的边，之后求以超级源为根的最小树形图。