题解 P4716 【【模板】最小树形图】

· · 题解

1 DAG的最小树形图

一个树形图中，除了r点其他点都只有一个入边

那么对于一个DAG，只要我们对于每一个点选出最小的入边，那么这一定是个树形图（显然，易证

那么算法就非常的简单

for(int i=1;i<=n;i++,des=r){
    for(int j=1;j<=n;j++)
        if(e[i][j]<e[i][des]&&i!=j)
            des=j;
    ans+=e[i][des];
}

2 环的最小树形图

这个问题十分傻，显然，从r开始绕一圈少一条边就行了

3 真正的最小树形图

这个东西叫做朱刘算法
好像伟大的图论专家塔扬先生有一种更好的方法，不过太烦了，没必要研究这种黑科技

我们看到，我们用DAG的算法把边分为了两种，红边就是要选的边，蓝边是因为比红边长而被抛弃的边，然后黄色的是个红边组成的环

如果我们一开始用DAG的贪心算出来的图就是一个一个DAG，那么皆大欢喜，这个环没有影响，直接输出即可

（这是一个逆时针的环）

1处理环

那么有环呢？

一旦有个环，那么这个环在选出来的图上肯定不会被其他点连接

那我们肯定要把其中一条边换成环外边

那么如果有环，我们就把贪心算出来的那个所谓的“树形图”上的环缩成一个点，环外边指向这个所称的点

为了方便统计，由于我们确信环外边的长度\ge环内边的长度，那么我们ans先加上这个环的边权和，然后指向环的边边权设为自己的长度-所连向的环内点在环中指向的点的边的长度

用那张图解释一下：

左上角的那个点，指向它的那条边，边权设为自己的长度，减去左上角的点到左下角的点的边的长度

有什么好处呢？

(引用一下别人的别人的别人的题解的图，这张图实在太好用了，放这里做参考)

这样，我们以后再选到这条边，就直接把它加到ans里面，就得到了这个环和连接这个环的边的所需长度了

为什么呢？易证，易得，显然如此，

假设环内去除的边权为x，连向这个环的边权为y，环的长度为k，那么这个环+连向这个环用的总长度应该是k-x+y，转换一下就是k+(y-x)，其中y-x就是那条连线环的边的边长

2 找环

说一遍，我不想TARJAN

fa[u]：u的入边另一个点，也就是u的“父亲”
tp[u]：相当于并查集路径压缩的数组，代表u的当前最早前驱
lp[u]：代表u是哪个环上的。如果lp=0，那么代表这个点目前还不是环上的

遍历每个节点u，然后沿着fa一路逆向走，直到根或者前驱是自己的点（路径压缩）或是环上点（一个点不可能处于两个环）。

如果最后走到了根，代表目前这个点还不是环上点

如果最后走到了前驱是自己的点v，分类讨论：

3 循环结束时间

总体的算法流程：对于每一次，求出所谓的“带环最小树形图”，然后把环缩点，修改边权

何时结束？

我们知道，一旦他是一个没有环的树形图，那么就是一个树形图了（雾

总的来说，一旦没有环，那么所有点都能到，那么就OK了，直接退出循环

撒花HORRAY

算法流程

对于每一次循环：

  1. 贪心找出所谓的“最小带环树形图”，（就是上面的万能图的红边）
    顺便记录一下自己是从哪里来的（入边的起点）
  2. 把所有选出的边加到ans里面
  3. 找环记录环，统计数量
  4. 如果没环，代表完成了，退出循环
  5. 把所有不是环上的点全部设置为自己是一个独立环（大小为1的新环）
  6. 重新设置边权&缩点
  7. 完成缩点，重新设置n和root，然后初始化
#include<bits/stdc++.h>
using namespace std;
const int N=109,M=10009; 
struct edge{int u,v,w;}e[M]; //用边表存储 

int n,m,root,mn[N],fa[N],tp[N],lp[N],tot,ans;
int zl(){
    while(1){
        for(int i=1;i<=n;i++) mn[i]=1e9,fa[i]=tp[i]=lp[i]=0;

        for(int i=1,u,v,w;i<=m;i++) //Step 1
            if(e[i].u!=e[i].v&&(w=e[i].w)<mn[v=e[i].v])
                mn[v]=w,fa[v]=e[i].u;
        mn[root]=0;
        for(int u=1;u<=n;u++){ans+=mn[u];if(mn[u]==1e9)return -1;} //Step 2

        for(int u=1,v=1;u<=n;u++,v=u){ //Step 3
            while(v!=root&&tp[v]!=u&&!lp[v]) tp[v]=u,v=fa[v];
            if(v!=root&&!lp[v]){
                lp[v]=++tot;
                for(int k=fa[v];k!=v;k=fa[k]) lp[k]=tot;
            }
        }
        if(!tot) return ans; //Step 4
        for(int i=1;i<=n;i++) if(!lp[i]) lp[i]=++tot; //Step 5

        for(int i=1;i<=m;i++) //Step 6
            e[i].w-=mn[e[i].v],e[i].u=lp[e[i].u],e[i].v=lp[e[i].v];
        n=tot, root=lp[root], tot=0; //Step 7
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&root);
    for(int i=1,u,v,w;i<=m;i++)
        scanf("%d%d%d",&u,&v,&w),e[i]=(edge){u,v,w};
    printf("%d",zl());
    return 0;
}

最后说一下个人的想法：

最小树形图在联赛中并不常见，但是zl算法却有一个很重要的思想：见到有向有环图，可以想到缩点，然后利用DAG的特性去做题，因为许多算法在 DAG 上可以有更优/更方便的解。