最小树形图 | 最小内向森林

最小树形图

对于带权有向图 \(G=(V,E)\)。

对于根 \(root\) 最小树形图为以 \(root\) 为根的外向树最小边权和。

有根树的树形图

对于确定的 \(root\) 求最小树形图。

朱刘算法

核心:

1. 对于有向图上的一个非根节点，对于它的所有入边加减一个权值 \(v\)，最优解的树形图形态不变。

因为所有非根点必然有一条入边，所以可以对于每个点，取入边边权最小值减去，把减去的部分加入答案。

经过这样的操作使得每条边边权非负，且每个点都有一条为 0 的入边。

2. 对于权非负的有向图上，如果存在一个边权均为0的环，可以把环上的点收缩。

因为无论最后得到的树形图如何连边，一定可以通过断掉环上的一条边来生成一个可行的树形图。

算法流程

1. 为每个点的入边更改边权

2. 收缩0环

   1. 存在环 : 回到1，
   2. 不存在环：结束算法。

此时存在两种情况

1. 图不连通，无解，

2. 图联通，每个点一定存在一条为 0 的入边，取出一个合法边集，然后依次展开每个被收缩的 0 环，即可得到一个最小树形图方案

复杂度分析：

每次收缩环需要依次遍历，每次至少缩小一个点，因此复杂度上限为 \(O(nm)\)。

Tips:

1. 注意不要更改根的入边。

2. 0 边构成的的图不连通。

实现：只记录一条 0 边指向的点，找环。

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)\)

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]; // F存连通块，J存编号
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)\)。