最小树形图（朱-刘算法）

概念导入：最小树形图可以简单的理解为树枝有方向的最小生成树，加上了方向的限制，使得得到它要稍微麻烦一点，解决这个问题的算法是朱永津与刘振宏在上世纪60年代提出的朱-刘算法（难得的中国人的算法）。

定义：设G = (V,E)是一个有向图，它具有下述性质：
1. G中不包含有向环；　
2. 存在一个顶点vi，它不是任何弧的终点，而V中的其它顶点都恰好是唯一的一条弧的终点；
则称 G是以vi为根的树形图。
最小树形图是有向图G = (V, E)中以vi为根的树形图中权值和最小的那一个。

完整的朱刘算法大体上有这四个步骤：
1、求最短弧集合E
2、判断集合E中有没有有向环，如果有转步骤3，否则转4
3、收缩环，把有向环收缩成一个点，并且对图重新构建，包括边权值的改变和点的处理，之后再转步骤1
4、展开收缩点，求得最小树形图

经典的算法图示：

这里推荐一篇将的比较不错的博客，详细过程见这一篇：
https://blog.csdn.net/qq_34731703/article/details/53965684
着重提一下收缩一个环后对图的处理：

该环最终将缩成e1点，其所有环外入边权要减去其环内入边权；环上到环外的出边中，连接到同一个点的，保留权值最小的那一条。

代码：

const int INF = 0x3f3f3f;
const int MAXN = 100;

int Map[MAXN][MAXN], n;
int pre[MAXN];
bool vis[MAXN], flag[MAXN];

void init()
{
    memset(vis, false, sizeof(vis));
    memset(flag, false, sizeof(flag));
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            Map[i][j] = INF;
}

int Zhuliu(int r)
{
    int ans = 0;
    init();
    while(true)
    {
        //求最短边集合
        for(int i = 1; i <= n; i++)//枚举每个不是根节点的点
            if(i != r && !flag[i])//flag标识是否点在有向环中且不是有向环的缩点
            {
                Map[i][i] = INF;
                pre[i] = i;//pre存i的前驱点，前驱->i有一条单向边，
                           //最终这条边要最短。
                           //初始化i的前驱为自己
                for(int j = 1; j <= n; j++)//枚举i的前驱j
                    if(!flag[j] && Map[j][i] < Map[pre[i]][i])
                        pre[i] = j;//找最短入边，pre存起来
                if(pre[i] == i) return -1;//如果当前点没有入边，则不存在最小树形图
            }
        //判断E中是否有环
        int e;
        for(e = 1; e <= n; e++)
            if(e != r && !flag[e])
            {
                int j = e, cnt = 0;
                while(j != r && pre[j] != e && cnt <= n)
                    j = pre[j], cnt++;//对每个点，不停找其前驱，找环
                if(j == r || cnt > n) continue;//找到根或经过数量超过n，无环
                else break;//否则有环，可以看出，程序最大的while中一次最多找到一个环
            }
        if(e > n)//如果E中没有环
        {
            for(int i = 1; i <= n; i++)
                if(i != r && !flag[i])
                    ans += Map[pre[i]][i];
            return ans;
        }
        else//如果有环
        {
            memset(vis, false, sizeof(vis));
            //缩环为点
            int o = e;//找环模块中找到环的断点
            while(true)//遍历环
            {
                ans += Map[pre[o]][o];//对环内的边权进行记录
                o = pre[o];
                vis[o] = flag[o] = true;//标记环内的点
                if(o != e) break;
            }
            flag[e] = false;//环被缩成了点e，依然存在
            //处理缩点后的图，对环外的相关边权进行改变
            for(int k = 1; k <= n; k++)
                if(vis[k])//缩环时标记出的环内的点
                    for(int j = 1; j <= n; j++)
                        if(!vis[j])
                        {
                            if(Map[e][j] > Map[k][j])
                                Map[e][j] = Map[k][j];//选择出边中最短的
                            if(Map[j][k] < INF && Map[j][k]-Map[pre[k]][k]<Map[j][e])
                                Map[j][e] = Map[j][k] - Map[pre[k]][k];
                                //按上文规则，入边减去环内对应边的权值
                        }
        }
    }
    return ans;
}