[复习资料]最小树形图

最近在整理自己的模板集，然后就发现了最小树形图这个基本不考的考点，我记得当时学最小树形图的时候都是迷迷糊糊的，跟着题解敲了一遍代码，根本无法理解这个算法，所以后面就直接忘了最小树形图咋写的。。。

现在回顾感觉包括优化都还是挺简单的，不知道当时自己怎么这么蠢。。。

最小树形图问题指的是：给定一个有向图，边有边权，给定根 \(r\) ，找到该图的一个子图使得 \(r\) 可以到达其他所有点（或者被其他所有点到达），最小化该子图的边权和。很显然，最后得到的子图结构一定是一个外向树（内向树），这里考虑内向树。

朴素的贪心思想，除了根以外每个点都恰好有一条出边，于是我们当然希望每个点都可以选择它所有出边中边权最小的那一条，如果这样选择后没成环最好，如果出现了一个环，那么这个环中只要一个点去改变它选择的出边，其它点就仍然能够保持原来的选择，所以自然最优的选择就是只去更改这个环中一个点的出边，或者说，整个环还需要一个额外的出边，这和一个点的要求相同！于是我们发现，整个环完全可以视作一个单独的点，不过这个点出边的边权需要做一些更改。

没有优化的朱刘算法就是每次找出边，然后缩点，缩点后再找出边，一直这样迭代，复杂度是 \(O(nm)\) 。

考虑优化，找最小值考虑堆，容易发现，一次缩环操作仅仅改变的是这个环内部点的出边，并且环内同一个点的出边边权都是同时加上一个值，然后再将所有出边合并，于是考虑可并堆，整体加不改变堆结构，所以可以实现，比如左偏树，左偏树用懒标记很容易就可以支持整体加。这样缩完点后就可以很快找到新的最小边权的出边。这个可以直接用 dfs 去实现，每次出现环了就地缩环就行。复杂度 \(O((n+m)\log m)\) 。

下面是代码：

#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
//最小树形图 
//Directed Minimum Spanning Tree
namespace DMST{
	const int maxn=105,maxm=10005;
	struct Val{
		int v,w;
		Val(int v=0,int w=0):
			v(v),w(w){}
		Val operator += (const int o){
			this->w=this->w+o;return *this;
		}
		bool operator < (const Val o)const{
			return w<o.w;
		}
	};
	struct Node{
		int l,r,dis,laz;Val v;
		Node(int l=0,int r=0,int dis=0,int laz=0,Val v=Val()):
			l(l),r(r),dis(dis),laz(laz),v(v){}
	}P[maxm];
	int tot;
	void push(int x,int laz){
		P[x].laz+=laz;
		P[x].v+=laz;
	}
	void pushdown(int x){
		if(!P[x].laz)return;
		push(P[x].l,P[x].laz);
		push(P[x].r,P[x].laz);
		P[x].laz=0;
	}
	void pushup(int x){
		if(P[P[x].l].dis<P[P[x].r].dis)
			std::swap(P[x].l,P[x].r);
		P[x].dis=P[P[x].r].dis+1;
	}
	int newnode(Val v){
		P[++tot]=Node(0,0,1,0,v);
		return tot;
	}
	void merge(int&x,int l,int r){
		if(!l||!r)return x=l|r,void();
		pushdown(l);pushdown(r);
		if(P[r].v<P[l].v)l^=r^=l^=r;
		x=l;merge(P[x].r,P[l].r,r);
		return pushup(x);
	}
	void pop(int&x){
		pushdown(x);
		merge(x,P[x].l,P[x].r);
	}
	int rt[maxn];
	int id[maxn];
	int vis[maxn],cnt;
	int st[maxn],tp;
	int find(int x){
		return id[x]==x?x:id[x]=find(id[x]);
	}
	#define inf 0x3f3f3f3f
	int dfs(int u){
		if(vis[u]&&vis[u]<cnt)return 0;
		if(vis[u]==cnt){
			while(st[tp]!=u){
				id[st[tp]]=u;
				merge(rt[u],rt[u],rt[st[tp]]);
				--tp;
			}
		}
		else vis[u]=cnt,st[++tp]=u;
		if(rt[u]==0)return -inf;
		Val tmp=P[rt[u]].v;
		pop(rt[u]);push(rt[u],-tmp.w);
		return tmp.w+dfs(find(tmp.v));
	}
	#undef inf
	//由于不用存图，这里直接输入了 
	int solve(void){
		int n,m,r;
		scanf("%d%d%d",&n,&m,&r);
		vis[r]=cnt=1;
		for(int i=1;i<=n;++i)
			id[i]=i;
		for(int i=1;i<=m;++i){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			merge(rt[v],rt[v],newnode(Val(u,w)));
		}
		int ans=0;
		for(int i=1;i<=n;++i){
			if(i!=r&&!vis[i]){
				++cnt;
				int tmp=dfs(i);tp=0;
				if(tmp<0)return -1;//无解 
				ans+=tmp;
			}
		}
		return ans;
	}
}
int main(){
	printf("%d\n",DMST::solve());
	return 0;
}