最小树形图

发表于 分类于

最小树形图的一些总结。

问题

给定一个 $n$ 个点 $m$ 条边的带边权的有向图，给定一个根 $rt$，问一棵以 $rt$ 为根的外向生成树的边权和的最小值。

$n\le 100,m\le 10^4$。

$n\le 10^5,m\le 5\times 10^5$。

朱-刘算法

除根节点 $rt$ 外，对于其他所有的点 $u$，记 $in[u]$ 连向 $u$ 的边中最短的边的权值，$pre[u]$ 为这条边的入点。

如果这些边不构成环，那么直接选这些边就是答案了。

如果构成环，考虑将一个环缩成一个点，变成一个子问题。

用反悔贪心，对于环内的点形成的边全部删掉，新建一个节点 $w$，对于环上的每个点 $v$，对于原图所有的边 $(u,v,z)$，其中 $u$ 不在环上，将这条边改成 $(u,w,z-in[v])$。

然后将环中所有的 $in[v]$ 都加进答案 $ans$ 里。然后考虑新图的答案。

如果遇到某个 $rt$ 外的点没有入边，则无解。

每次图至少减少一个点，每次的时间复杂度为 $O(n+m)=O(m)$。时间复杂度 $O(nm)$。

优化

这个优化是Tarjan提出的，能将算法优化到 $O(n+m\log m)$。

考虑将朱-刘算法的步骤改一下，变成每次加一条边进去，答案加上这条边的权值，这条边的出点为上一次加进去的入点。直到碰到已加入的点为止。如果成环则处理这个环，否则不处理。

重复上面的过程，直到所有点都被标记过，用并查集维护每个点在新图中被合并成哪个点。

考虑处理一个环会发生什么，将所有边扔进去出点中形成一个集合，相当于删掉这个集合中的一个，剩下的同时减去一个值，然后合并，且会查询最小值。

这个显然可以用带懒惰删除的和整体加标记的可并小根堆维护。

时间复杂度 $O(m\log m)$。

代码

需要注意的是，处理完环后，可并堆中维护的节点信息会改变，查询最小值时需要用并查集更新找到当前连着的真正的点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=200010;
int find(int x);
struct node{
	int val,v,id;
	friend inline bool operator>(const node &A,const node &B)
	{
		return A.val>B.val;
	}
};
struct Heap{
	node v[N];
	int dis[N],ls[N],rs[N],tag[N];
	bool del[N];
	int rt[N];
	inline void pushtag(int u,int t)
	{
		if(u) tag[u]+=t,v[u].val+=t;
	}
	inline void pushdown(int u)
	{
		if(!tag[u]) return;
		pushtag(ls[u],tag[u]);
		pushtag(rs[u],tag[u]);
		tag[u]=0;
	}
	int merge(int x,int y)
	{
		if(!x||!y) return x+y;
		if(v[x].val>v[y].val) swap(x,y);
		pushtag(y,-tag[x]);
		rs[x]=merge(rs[x],y);
		if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
		dis[x]=dis[rs[x]]+1;
		return x;
	}
	inline int pop(int x)
	{
		pushdown(x);
		return merge(ls[x],rs[x]);
	}
	inline void ins(int y,int va,int id,int to)
	{
		v[id]=(node){va,to,id};
		rt[y]=merge(rt[y],id);
	}
	inline void dec(int id,int v) {pushtag(id,-v);}
	inline node top(int u)
	{
		for(;rt[u]&&find(v[rt[u]].v)==u;) rt[u]=pop(rt[u]);
		if(!rt[u]) {printf("-1"); exit(0);}
		v[rt[u]].v=find(v[rt[u]].v);
		return v[rt[u]];
	}
};
Heap h;
int fa[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void Union(int u,int v)
{
	u=find(u); v=find(v);
	if(u==v) return;
	h.rt[v]=h.merge(h.rt[u],h.rt[v]),fa[u]=v;
}
int n,m,rt,pre[N],bel[N];
ll ans;

int main()
{
	n=read(); m=read(); rt=read();
	int x,y,z;
	fo(i,1,m)
	{
		x=read(),y=read(),z=read();
		h.ins(y,z,i,x);
	}
	int cnt=n;
	node now;
	bel[rt]=rt;
	fo(i,1,n<<1) fa[i]=i;
	fo(i,1,n)
	{
		int j=i;
		for(;!bel[j];)
		{
			while(!bel[j]) bel[j]=i,now=h.top(j),ans+=now.val,j=now.v;
			if(bel[j]!=i) break;
			for(;bel[j]!=-1;) bel[j]=-1,j=pre[j]=(now=h.top(j)).v,h.dec(now.id,now.val);
			++cnt;
			for(;bel[j]!=i;) bel[j]=i,Union(j,cnt),j=pre[j];
			j=cnt;
		}
	}
	printf("%lld",ans);
	return 0;
}