最小树形图-朱刘算法-学习笔记-解题报告-P4716

## 题意 给定一张**有向图**，求出以给定节点为根的最小树形图；树形图的定义是，从根节点出发可以到达所有其他点（所以图首先要联通） ## 实现   总的来说： 1. 求最短弧集合E； 2. 判断集合E中有没有有向环，如果有转步骤3，否则转4； 3. 收缩点，把有向环收缩成一个点，并且对图重新构建，包括边权值的改变和点的处理，之后再转步骤1； 4. //展开收缩点，求得最小树形图； 　　(1)求最短弧集合E0. 　　从所有以Vi(i ≠ 0)为终点的弧中取一条最短的,若对于点i,没有入边,则不存在最小树形图,算法结束;如果能取,则得到由n个点和n-1条边组成的图G的一个子图G',这个子图的权值一定是最小的,但是不一定是一棵树. ``` for(ri i=1; i<=n; ++i) ine[i]=inf; // 初始化 for(ri i=1; i<=m; ++i) { int u=e[i].u,v=e[i].v; if(u!=v&&e[i].w<ine[v]) // 遍历所有边，对每个点找到最小的入边 ine[v]=e[i].w,pre[v]=u; } ``` **找到以每个点为终点的边的最小值并记录；根没有入边；被缩的点忽略；如果从一个点没有入边，一定不存在树形图；** 　　(2)检查E0. 　　若E0没有有向环且不包含收缩点,则计算结束,E0就是G以V0为根的最小树形图,若E0没有有向环,但是存在收缩点,转到步骤(4),若E0含有有向环,则转入步骤(3). 如果没有环，那么选出来的就是树形图；否则就要缩点； ``` for(ri i=1; i<=n; ++i) vis[i]=id[i]=0; for(ri i=1; i<=n; ++i) { if(i==root) continue; ans+=ine[i]; int v=i; while(vis[v]!=i&&!id[v]&&v!=root) // 找环 { vis[v]=i; v=pre[v]; } if(!id[v]&&v!=root) { id[v]=++cnt; // 把环上的店标记为同一点 for(ri u=pre[v]; u!=v; u=pre[u]) id[u]=cnt; } } ``` **一定要记录cnt或开一个bool数组记录走过的边，不然可能疯狂走环；** 　　(3)收缩G中的有向环. 　　把G中的环C收缩成点u,对于图G中两端都属于C的边就会被收缩掉,其他弧仍然保留,得到一个新的图G1,G1中以收缩点为终点的弧的长度要变化,变化的规则是:设点v在环C中,且环中指向v的边的权值为w,点v'不在环C中,则对于G中的每一条边<v', v>,在G1中有边<v', u>和其对应,且权值WG1(<v', u>) = WG(<v', v>) - w;对于图G中以环C中的点为起点的边<v', v>,在图G1中有边<u, v'>,则WG1(<u, v'>) = WG(<v', v>).有一点需要注意,在这里生成的图G1可能存在重边. 　　对于图G和G1: 　　<1>:如果图G1中没有以v0为根的最小树形图,则图G也没有. 　　<2>:如果G1中有一v0为根的最小树形图,则可按照步骤(4)的展开方法得到图G的最小树形图. 　　所以,应该对于图G1代到(1)中反复求其最小树形图,直到G1的最小树形图u求出. **缩环的时候记得加入答案，环上的出边直接接上，入边要注意，选一条入边相当于删掉一条环边，所以加入入边的权值为$w-ine[v]$** 　　(4)展开收缩点. ## 扩展：无根树的树形图 ~~以写挂了的HDU2121为例~~ 不限定根结点的树形图，我们可以虚拟一个0号根节点，并向各个点连一条权值为$sum(w)+1$的边，因为权值很大，所以最终结果一定只包含一条这样的边；但是如果答案大于$sum+sum+1$，其实是无解的，这样相当于两个点不联通，只好多选一条大边；否则答案是$ans-sum-1$ 如果要输出编号最小的根节点，多解的情况一定是有环，而超级源点最后选择的一条出边一定就是最优解（多加的边按照点的编号排序）；所以我们就在找边的时候加上一句就好了； ``` if (u == root) pos = i; ``` 那么答案即为pos-m-1（pos为边的编号） ## 易错 1.非常重要，不然T飞：在判环时一定要加上cnt计数，并在cnt>n时break；否则就开一个bool数组记录是否经过该点；不然可能会有一个环然后就在里面不停转； 2.缩点时，变量名不要写错…… ## 代码 ``` struct Edge { int u,v,w; } e[M]; const int inf=2e9; int n,m,root; int pre[N],ine[N]; int vis[N],id[N]; int zhuliu() { int ans=0; while(1) { for(ri i=1; i<=n; ++i) ine[i]=inf; // 初始化 for(ri i=1; i<=m; ++i) { int u=e[i].u,v=e[i].v; if(u!=v&&e[i].w<ine[v]) // 遍历所有边，对每个点找到最小的入边 ine[v]=e[i].w,pre[v]=u; } for(ri i=1; i<=n; ++i) // 判定无解 if(i!=root&&ine[i]==inf) return -1; int cnt=0; for(ri i=1; i<=n; ++i) vis[i]=id[i]=0; for(ri i=1; i<=n; ++i) { if(i==root) continue; ans+=ine[i]; int v=i; while(vis[v]!=i&&!id[v]&&v!=root) // 找环 { vis[v]=i; v=pre[v]; } if(!id[v]&&v!=root) { id[v]=++cnt; // 把环上的店标记为同一点 for(ri u=pre[v]; u!=v; u=pre[u]) id[u]=cnt; } } if(cnt==0) break; // 无环，得到解 for(ri i=1; i<=n; ++i) if(!id[i]) id[i]=++cnt; for(ri i=1; i<=m; ++i) { int u=e[i].u,v=e[i].v; e[i].u=id[u],e[i].v=id[v]; if(id[u]!=id[v]) e[i].w-=ine[v]; // 修改边权 } root=id[root]; n=cnt; } return ans; } ```