最小树形图
akioieverycentury
·
·
算法·理论
最小树形图
luogu 和 oiwiki 上都有讲解，但有些地方讲得太冗杂，有些地方太省略，本蒟蒻在这里整合一下，不说废话。
定义
（你可以选择直接看下一段）一棵外向树就是除了根节点（没有入边）之外，每个节点都有且仅有一条入边。那么在一个有向图中，以一个给定节点为根节点且包含了该图中的所有节点的外向树，就是这个有向图的一个树形图。其中边权和最小的一种树形图就是最小树形图。
说的有点麻烦，一句话，就是有向图的最小生成树，但必须保证边的方向是由根节点向外扩散的。
求解
求解最小树形图有两种算法，分别是朱刘算法（复杂度 \mathcal O(nm+n^2)）和 Tarjan 发明的 DMST，其实就 Directed MST，MST 是最小生成树，复杂度 \mathcal O(m+n\log m)，可以用斐波那契堆优化到 \mathcal O(m+n\log n)。
这里讲解朱刘算法。
先考虑如果是一个有向无环图，那么对于每一个非根节点，我们可以贪心地选一条边权最小的入边。这样选出的所有点和边就构成了这个有向无环图的最小树形图。这很显然
再单独考虑一个环，如果根在环内，只需把根的入边拆断；环内无根，则拆断一条权值最大的边。这也很显然。
两种情况合起来，我们考虑一个有向图：
无环的部分，按照前面所说的有向无环图处理即可，而对于环来说：为了保证每个非根节点有且仅有 1 条入边（树形图的定义），在断开环内一条边时，还需给断开的边所指向的点连接一条指向它的新边，也就是环外的边。从环外连的这条边就会顶替掉它指向的环内的节点原来的入边。
还要注意，这里有一个处理技巧：由于环内每一个点初始默认它选择的入边是环内边，那么换成环外边时对答案的贡献应为 ans=ans-w_{in}+w_{out}（其中 w_{in} 是环内边边权，w_{out} 是环外边边权），因此在找到环时直接令环上每个点的环外边边权 = 该边原边权 - 所指向点的环内边边权。这样以来断开环的时候只需仿照无向图一样贪心的选择最小边权，直接加上就对答案产生贡献。（其实这个地方挺简单的，我感觉我写的有点啰嗦了，看懂就行）
这样，程序中我们只需要反复进行这两个操作：
- 找到每个点的最小入边边权。
- 检测是否有环：有则把它缩成点，当成新的点去做上一步；无环则输出答案结束程序。
具体地，我在这里讲一个洛谷题解区广为流传的图片，他们讲得不是很详细（这导致我对图的某些地方疑惑了很久），我详细说一下：
这个过程有五步：
-
找到一个简单环 2,3,4，ans 直接加上这个环内的边权。
-
我们把这个环缩成点，这个点的入边（先前说的环外边）的权值就应该更改为它加进来后的贡献（即这个边的边权减去这个边所指向的原来被缩点之前的环内的点的入边的边权，前面也提到了），因此 1 指向 2,3,4 的边权 4 减去 1 所指向的点 4 的入边边权 2，等于 2，5\rightarrow 2,3,4 同理。
-
找到了一个新环：5-2,3,4，ans 直接加上这个环的边权。
-
和第二步同理，更新 1 加进来时对答案的新贡献。
-
对 2,3,4,5 这个点找到最小入边边权，加到 ans 里面。
终于写完了。
实现
你可以写一个 Tarjan 找强连通，有点大材小用。
下面给一个简单的做法：
$ffa_u$ 表示 $u$ 的超级祖先（最早前驱）。
$cc_u$ 表示 $u$ 所在环的编号，$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=+\infty$，直接无解，结束；当整个图上没有环时，统计好答案后就可直接输出了，因为这是有向无环图的那一类情况。
我觉得说到这基本可以自己写出来了。提供代码以便于明确一些细节实现：
```cpp
#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;
}
```
终于结束了，咕咕嘎嘎。
## 例题 [P2792 \[JSOI2008\] 小店购物](https://www.luogu.com.cn/problem/P2792)
读完题很容易想到大体思路为根据这 $k$ 个优惠政策建立有向边，然后在建好的图上跑一边最小树形图，这个题就做完了。
接下来考虑一些实现的细节：
1. 总有一些商品按“原价”买（即不出现在优惠有向边的末点位置），我们不妨建立一个超级根节点，让这个点向所有无入边的节点建立有向边，以超级根节点为 $root$ 跑一遍。
2. 考虑这个情况：有两个商品互相指向对方，那么先把其中一个全买再去买另一个显然是不优的，应该先买一个某个商品，这样两个商品都有优惠。具体地，每个节点本来表示每个商品要买 $t_i$ 次，将其拆成两个节点，表示这个商品买 $1$ 次和买 $t_i-1$ 次。
然后上 code：
```cpp
#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;
double w;
}a[N];
int fa[N];
int ffa[N];
int cc[N],vis[N];
int n,m,root;
int tot;
double ans,mn[N],s[N];
int id[N][2];
int t[N];
int k;
int idx;
inline void inits(){
for(int i=1;i<=n;i++)mn[i]=0x3f3f3f3f3f3f3f3f;
memset(fa,0,sizeof fa);
memset(vis,0,sizeof vis);
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;
}
mn[root]=0;
for(int i=1;i<=n;i++){
ans+=mn[i];
int now=i;
while(now!=root&&vis[now]!=i)vis[now]=i,now=fa[now];
if(now!=root&&!cc[now]){
cc[now]=++tot;
while(now!=root&&!cc[fa[now]]){
now=fa[now];
cc[now]=tot;
}
}
}
if(!tot)return;
for(int i=1;i<=n;i++)if(!cc[i])cc[i]=++tot;
for(int i=1;i<=m;i++){
if(a[i].u!=a[i].v)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();
root=++idx;
for(int i=1;i<=n;i++){
cin>>s[i]>>t[i];
if(t[i]>0)id[i][0]=++idx,a[++m]=(node){root,id[i][0],s[i]};
if(t[i]>1)id[i][1]=++idx,a[++m]=(node){root,id[i][1],s[i]*(t[i]-1)};
}
k=re();
for(int i=1;i<=k;i++){
int u=re(),v=re();
double w;cin>>w;
if(t[u]>0&&t[v]>0)a[++m]=(node){id[u][0],id[v][0],w};
if(t[u]>0&&t[v]>1)a[++m]=(node){id[u][0],id[v][1],w*(t[v]-1)};
if(t[u]>1&&t[v]>0)a[++m]=(node){id[u][1],id[v][0],w};
if(t[u]>1&&t[v]>1)a[++m]=(node){id[u][1],id[v][1],w*(t[v]-1)};
}
n=idx;
zhuliu();
cout<<fixed<<setprecision(2)<<ans;
return 0;
}
```
一些非常致命的注意事项（这导致我调了很久很久，真的很久很久）：
1. 能不能建边取决于购买次数和 $0$ 的大小关系，能不能拆点取决于购买次数和 $1$ 的大小关系。
2. 点的编号一定要从 $1$ 开始且连续，拆点我本来写的 $i$ 和 $i+n$，但如果中间有一些点的攻击次数为 $0$ 这样点编号不连续调那个 $\operatorname{zhuliu}$ 函数相当麻烦。所以每次加新点就用了 $idx$，而且一定要记得跑 $\operatorname{zhuliu}$ 之前令 $n=idx$。
3. 找环的过程放进了统计答案里面，因为根据题意建出来的图不一定联通。而且环处理的时候一定要谨慎一点，想明白了再写。