最小树形图 | 最小内向森林
最小树形图
对于带权有向图$G=(V,E)$
对于根$root$最小树形图为以$root$为根的外向树最小边权和
有根树的树形图
对于确定的$root$求最小树形图
朱刘算法
核心:
1:对于有向图上的一个非根节点，对于它的所有入边加减一个权值$v$，最优解的树形图形态不变
因为所有非根点必然有一条入边，所以可以对于每个点，取入边边权最小值减去，把减去的部分加入答案
经过这样的操作使得每条边边权非负，且每个点都有一条为0的入边
2:对于权非负的有向图上，如果存在一个边权均为0的环，可以把环上的点收缩
因为无论最后得到的树形图如何连边，一定可以通过断掉环上的一条边来生成一个可行的树形图
算法流程
1.为每个点的入边更改边权
2.收缩0环
2.1 存在环 : 回到1
2.2 不存在环：结束算法
此时存在两种情况
1.图不连通，无解
2.图联通，每个点一定存在一条为0的入边，取出一个合法边集，
然后依次展开每个被收缩的0环，即可得到一个最小树形图方案
复杂度分析：
每次收缩环需要依次遍历，每次至少缩小一个点，因此复杂度上限为$O(nm)$
Tips:
1.注意不要更改根的入边
2.0边构成的的图不连通
实现：只记录一条0边指向的点，找环
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
| const int N=10010,INF=1e9;
int n,m,rt,ans;
int U[N],V[N],W[N];
int id[N],inw[N],pre[N];
void Reweight(){
rep(i,1,n) inw[i]=INF,pre[i]=0;
rep(i,1,m) if(U[i]!=V[i] && V[i]!=rt) if(inw[V[i]]>W[i]) inw[V[i]]=W[i],pre[V[i]]=U[i];
rep(i,1,n) if(i!=rt && id[i]==i) {
if(inw[i]==INF) puts("-1"),exit(0);
ans+=inw[i];
}
rep(i,1,m) if(U[i]!=V[i] && V[i]!=rt) W[i]-=inw[V[i]];
}
int vis[N];
int Union(){
int fl=0;
rep(i,1,n) vis[i]=0;
rep(i,1,n) if(id[i]==i && !vis[i]) {
int u=i;
while(u && !vis[u]) vis[u]=i,u=pre[u];
if(vis[u]==i) {
int v=pre[u];
fl=1;
while(v!=u) id[v]=u,v=pre[v];
}
}
return fl;
}
int main(){
n=rd(),m=rd(),rt=rd();
rep(i,1,n) id[i]=i;
rep(i,1,m) U[i]=rd(),V[i]=rd(),W[i]=rd();
while(1) {
Reweight();
if(!Union()) break;
rep(i,1,m) U[i]=id[U[i]],V[i]=id[V[i]];
rt=id[rt];
}
printf("%d\n",ans);
}
|
可并堆优化朱刘算法
涉及到的操作：
1.依次插入每个点，为其确定一条最小的出边
2.如果出边（0边）构成了环，将环上的点缩点
3.合并环上点的点出边集合，并将这个点重新加入待定点集
3操作要用可并堆维护合并点集入边的最小权值，并且支持全局减操作
2操作用并查集维护判断是否出现了环，我写得比较丑，一个并查集存缩点之后新点的编号，一个存点所在连通块
比较常见的实现是左偏树，因为便于全局修改的标记下传操作，代码也比较好写
用可并堆维护朱刘算法的操作，单次合并操作为$O(\log m)$，因此复杂度为$O((n+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
| const int N=100010;
int n,m,rt,ans;
class Heap{
private:
Heap *ls,*rs;
Pii val;
int tag,dis;
void Down(){
if(ls) ls->val.first+=tag,ls->tag+=tag;
if(rs) rs->val.first+=tag,rs->tag+=tag;
tag=0;
}
void Up(){
if(rs && (!ls || rs->dis>ls->dis)) swap(ls,rs);
dis=rs?rs->dis+1:1;
}
public:
Heap(){ }
Heap(Pii x){ ls=rs=0,val=x,tag=0,dis=1; }
friend Heap* Union(Heap* a,Heap *b) {
if(!a) return b;
if(!b) return a;
if(a->val>b->val) swap(a,b);
a->Down(),a->rs=Union(a->rs,b);
return a->Up(),a;
}
void Add(int x){ tag+=x,val.first+=x; }
Pii top(){ return val; }
Heap* pop(){ return Down(),Union(ls,rs); }
} *H[N];
int F[N],J[N];
Pii G[N];
int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]); }
int I(int x){ return J[x]==x?x:J[x]=I(J[x]); }
void Work(int i) {
while(H[i] && I(H[i]->top().second)==i) H[i]=H[i]->pop();
if(!H[i]) puts("-1"),exit(0);
G[i]=H[i]->top(),H[i]->Add(-G[i].first),H[i]=H[i]->pop();
ans+=G[i].first;
int v=I(G[i].second);
if(Find(i)!=Find(v)) F[Find(i)]=Find(v);
else {
for(int u=v;u!=i;u=I(G[u].second)) J[I(u)]=i,H[i]=Union(H[i],H[u]);
Work(i);
}
}
int main(){
n=rd(),m=rd(),rt=rd();
rep(i,1,n) J[i]=F[i]=i;
rep(i,1,m) {
int u=rd(),v=rd(),w=rd();
H[v]=Union(H[v],new Heap(mp(w,u)));
}
rep(i,1,n) if(I(i)==i && i!=rt) Work(i);
printf("%d\n",ans);
}
|
无根树的最小树形图
建立超级原点$S$向$V$中的点连边权极大的边，以限制每次只选一条这样的边
单次得到答案后减去这个极大值即可，注意如果答案中出现多个这样的极大值，说明原图无解是无解的
最小内向森林
对于给定的值$k$，最小内向森林是一个有根树集合，且其恰好包含$k$条边
凸优化+朱刘算法
最小内向森林问题是一个凸函数问题，可以考虑$\text{wqs}$二分
同样建立超级原点$S$，二分原点$S$向$V$中点连的边权$\alpha$
通过朱刘算法得到新图的最小树形图
二分使得最终的树形图包含原点度数为$|V|-1-k$即可
优先内向树扩张算法
考虑在上面二分的过程中，一个点向原点连边当且仅当这个点不再有边边权$<\alpha$
同时一旦这个点向原点连边，就不再会与其他任何点合并
也就是这点的所有出边再减去下一条最小树边权值之后，存在一个$\alpha’<0$
容易想到按照每个点最小边的边权为优先级进行操作
最后被扩展的边的实际上就是我们要找的$\alpha$
令$dec_u$表示$u$节点中，被合并上来所有节点已经减掉的值的最大值
$dec_u’=dec_u+\min \{w_{v,u} \}$，合并时$dec_u$取$\max$
按照$dec’_u$递增的顺序考虑每个点的扩张，最后一个$dec’_u$就是我们所需要的$\alpha$
用一个额外的堆维护$dec’_u$的权值，直到扩张满$k$次即可
复杂度为$O((n+m)\log m+n\log n)$
