最小树形图

luogu和oiwiki上都有讲解，但有些地方讲得太冗杂，有些地方太省略，我在这里整合一下，不说废话。

1.什么是最小树形图？

一棵外向树就是除了根节点（有0条入边）之外，每个节点都有且仅有1条入边。那么在一个有向图中，以一个给定节点为根节点且包含了该图中的所有节点的外向树，就是这个有向图的一个树形图。其中边权和最小的一种树形图就是最小树形图。

说的有点麻烦，一句话，就是有向图的最小生成树，但必须保证边的方向是由根节点向外扩散的。

可以参考一下豆包的回答。

2.怎么求解？

求解最小树形图有两种算法，分别是朱刘算法（复杂度 $O(n(n+m))$ ）和 $Tarjan$ 发明的 DMST（其实就 Directed MST，MST 是最小生成树，复杂度 $O(m+nlogm)$ ，可以用斐波那契堆优化到 $O(m+nlogn)$ ）。

这里讲解朱刘算法。

先考虑如果是一个有向无环图，那么对于每一个非根节点，我们可以贪心地选一条边权最小的入边。这样选出的所有点和边就构成了这个有向无环图的最小树形图。这很显然

再单独考虑一个环，如果根在环内，只需把根的入边拆断；环内无根，则拆断一条权值最大的边。这也很显然。

两种情况合起来，我们考虑一个有向图：

无环的部分，按照前面所说的有向无环图处理即可，而对于环来说：为了保证每个非根节点有且仅有1条入边（树形图的定义），在断开环内一条边时，还需给断开的边所指向的点连接一条指向它的新边，也就是环外的边。从环外连的这条边就会顶替掉它指向的环内的节点原来的入边。

还要注意，这里有一个处理技巧：由于环内每一个点初始默认它选择的入边是环内边，那么换成环外边时对答案的贡献应为 $ans=ans-环内边边权+环外边边权$ ，因此在找到环时直接令环上每个点的环外边边权=该边原边权-所指向点的环内边边权。这样以来断开环的时候只需仿照无向图一样贪心的选择最小边权，直接加上就对答案产生贡献。（其实这个地方挺简单的，我感觉我写的有点啰嗦了，看懂就行）

这样，程序中我们只需要反复进行这两个操作：

1. 找到每个点的最小入边边权。
2. 检测是否有环：有则把它缩成点，当成新的点去做上一步；无环则输出答案结束程序。

具体地，我在这里讲一个luogu题解区广为流传的图片，他们讲得不是很详细（这导致我对图的某些地方疑惑了很久），我详细说一下：

这个过程有5步：

$Step1.$ 找到一个简单环 $2-3-4$ ， $ans$ 直接加上这个环内的边权。

$Step2.$ 我们把这个环缩成点，这个点的入边（先前说的环外边）的权值就应该更改为它加进来后的贡献（即这个边的边权减去这个边所指向的原来被缩点之前的环内的点的入边的边权，前面也提到了），因此 $1$ 指向 $234$ 的边权 $4$ 减去 $1$ 所指向的点 $4$ 的入边边权 $2$ ，等于 $2$ ， $5->234$ 同理。

$Step3.$ 找到了一个新环： $5-234$ ， $ans$ 直接加上这个环的边权。

$Step4.$ 和 $Step2$ 同理，更新 $1$ 加进来时对答案的新贡献。

$Step5.$ 对 $2345$ 这个点找到最小入边边权，加到 $ans$ 里面。

终于写完了。

3.怎么实现？

你可以写一个tarjan找强连通，有点大材小用。

下面给一个朴素做法：

fa[u]表示 $u$ 的入边的起点，即 $u$ 的父亲。

ffa[u]表示 $u$ 的超级祖先（最早前驱）。

cc[u]表示 $u$ 所在环的编号（cc是circle），$cc[u]=0$ 表示这个局面下 $u$ 不在环里。

mn[u]表示我们贪心地选择入边边权时的最小值。

把每个节点 $u$ 遍历一遍，遍历时顺着 $fa[u]$ 一直往上走，如果最后走到根节点，说明 $u$ 不在环上；如果最后走到一个点 $v$ 满足 $ffa[v]=u$ ，那么如果 $cc[v]$ 里面有东西，那 $v$ 肯定已经在别的环内，不管，否则 $cc[v]$ 里面没东西，这样我们就找到了一个新环，从 $u$ 到 $v$ 把这些点的 $cc$ 值全部赋为相同环编号值即可。

关于程序终止条件：无非两种情况，第一种是维护完 $mn[u]$ 后仍旧存在一个非根节点的 mn[u]=0x3f ，直接无解，结束；当整个图上没有环时，统计好答案后就可直接输出了，因为这是有向无环图的那一类情况。

我觉得说到这基本可以自己写出来了。提供代码以便于明确一些细节实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int re(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
const int N=1e4+10;
struct node{
	int u,v,w;
}a[N];
int fa[N];
int ffa[N];
int cc[N];
int n,m,root;
int mn[N];
int tot,ans;
inline void inits(){
	memset(mn,0x3f,sizeof mn);
	memset(fa,0,sizeof fa);
	memset(ffa,0,sizeof ffa);
	memset(cc,0,sizeof cc);
	tot=0;
}
inline void zhuliu(){
	while(1){
		inits(); 
		for(int i=1;i<=m;i++){
			if(a[i].u!=a[i].v&&a[i].w<mn[a[i].v]){
				mn[a[i].v]=a[i].w;
				fa[a[i].v]=a[i].u;
			}
		}
		for(int i=1;i<=n;i++){
			if(i!=root&&!fa[i]){
				ans=-1;
				return;
			}
		}
		for(int i=1;i<=n;i++)ans+=mn[i];
		for(int u=1,v=1;u<=n;u++,v=u){//找环  
			while(v!=root&&ffa[v]!=u&&!cc[v])ffa[v]=u,v=fa[v];
			if(v!=root&&!cc[v]){//即ffa[v]==u  
				cc[v]=++tot;
				for(int k=fa[v];k!=v;k=fa[k])cc[k]=tot;
			}
		}
		if(!tot)return; 
		for(int i=1;i<=n;i++)if(!cc[i])cc[i]=++tot;
		for(int i=1;i<=m;i++){
			a[i].w-=mn[a[i].v];//更新环外边的贡献  
			a[i].u=cc[a[i].u];
			a[i].v=cc[a[i].v];
		}
		n=tot,root=cc[root];//初始化缩点后的局面 
	}
}
signed main(){
	n=re(),m=re(),root=re();
	for(int i=1;i<=m;i++)a[i]=(node){re(),re(),re()};
	zhuliu();
	cout<<ans;
	return 0;
}

终于结束了，咕咕嘎嘎。

这是平台上例题【2025-11-05 P4】攻占，可以看看我发的题解。