Skip to content

Tag Archives: 最小树形图

最小树形图

最小树形图就是给定一个有向图,求以某个给定顶点为根的有向生成树(也就是说沿着这N-1条有向边可以从根走到任意点),使权和最小。 解决这个问题有一个O(VE)的算法,是这样的:对于除根外的每个顶点,选择一条权最小的入边。如果选出来的V-1条边不构成环,则可以证明这些边就是满足要求的答案。如果存在环,则将环中的边收缩成一个顶点。设x是环中的点,y不是环中的点,v为新的顶点,w0为上一步中x选择的入边的权值,则原来的权值为w的边(x,y)变成权值为w的边(v,y),原来的权值为w的边(y,x)变成权值为w-w0的边(y,v)。这时最小树形图的答案就是环的权值和加上收缩以后的图的答案。 为什么收缩了以后要减小权值呢?很简单,最小树形图需要每个顶点选一条入边,顶点x当前已经有入边了,如果以后再给收缩后的顶点x选择权值为w的(原来属于x的)入边,就意味着已经选择的那条权值为w0的入边可以去掉了,也就是说选择这条边的代价应该是w-w0,所以就做这样的修改。 不过如果不固定根,我还不太知道如何用同样的复杂度解决,谁写过请教教我。 (发现自己最近表达能力很差,这个文章说得清楚些。) 示例程序(TJU2248,用邻接矩阵写的,O(V^3),比较简洁): tju2248.cpp