<h1>前置定义</h1>

树形图：在一个有向图中，满足存在一个入度为 $0$ 的点，除了该点入读均为 $1$，且该图不存在环，那么称为树形图。
最小树形图：给定有向边权图，求以某点为根的边权和最小的子图，满足该子图为树形图。

<h1>朱刘算法</h1>

模板链接
相当于是一种贪心的思想。
首先我们发现一个合法的树形图中除根外的每个点只有一条入边，所以我们就贪心的选择原图中所有入边中最小的。但是注意到这样选出来的子图可能会存在环，所以我们可以暴力把这些环缩起来然后在新图中跑上述过程一直到找不到环为止。
但是注意到我们每此跑了一遍算法后，答案已经加上每个点的最短入边了，为了防止重复计算答案，要把其他的边长减去原来的最短入边边长，然后继续计算。
代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 100+5;
const int MAXM = 20000+5;

struct Edge{
    int u,v,w;
}e[MAXM];
int N,M,root,ans,cnt;
int in[MAXN],id[MAXN],vis[MAXN],pre[MAXN];

int main(){
    scanf("%d%d%d",&N,&M,&root);
    FOR(i,1,M) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    while("Shq AK IOI"){
        cnt = 0;
        FOR(i,1,N) in[i] = INT_MAX,id[i] = vis[i] = 0;
        FOR(i,1,M)
            if(e[i].u != e[i].v && e[i].w < in[e[i].v])
                pre[e[i].v] = e[i].u,in[e[i].v] = e[i].w;
        in[root] = 0;
        FOR(i,1,N){
            if(in[i] == INT_MAX){
                printf("%dn",-1);return 0;
            }
            ans += in[i];int u;
            for(u = i;u != root && vis[u] != i && !id[u];u = pre[u]) vis[u] = i;
            if(u != root && !id[u]){
                id[u] = ++cnt;
                for(int v = pre[u];v != u;v = pre[v]) id[v] = cnt;
            }
        }
        if(!cnt){
            printf("%dn",ans);
            return 0;
        }
        FOR(i,1,N) if(!id[i]) id[i] = ++cnt;
        FOR(i,1,M){
            int t = in[e[i].v];
            if((e[i].u = id[e[i].u]) != (e[i].v = id[e[i].v]))
                e[i].w -= t;
        }
        N = cnt;root = id[root];
    }
    return 0;
}

<h1>实际运用</h1>

接下来我们看一道例题：题目链接
（权限题，若查看不了请点击）
首先发现我们对于所有要买的东西，只需要第一次都买过一边后，剩下的都用优惠价格购买就可以了。
所以第一次以后的购买总额我们可以计算出来了，关键是确定所有物品第一次的购买顺序。
我们对于每一个物品都看作一个节点，考虑建立一个虚拟节点 $S$ ，连向所有物品一条长度为该物品第一次购买的价格；如果 $u$ 购买后能给予 $v$ 优惠，那么我们就从 $u$ 向 $v$ 连长度为优惠后的价格的边。
考虑这张图的最小树形图的意义：所有的点都被选择且选择总代价最小。
那么这个题目注意下 double 精度问题就可以过了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define Re register
#define LL long long
#define MP std::make_pair
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 50+5;
const double EPS = 1e-8;
const int MAXM = 100000+5;

struct Edge{
    int u,v;double w;
}e[MAXM<<1];
int N,M,cnt,root,tot;
int b[MAXN],vis[MAXN],id[MAXN],pre[MAXN];
double a[MAXN],ans,in[MAXN];

inline bool equal(double a,double b){
    return std::fabs(a-b) <= EPS;
}

inline void add(int u,int v,double w){
    e[++cnt] = (Edge){u,v,w};
}

inline void work(){
    root = 1;
    while(true){
        //DEBUG(N);
        int tot = 0;
        FOR(i,1,N) id[i] = vis[i] = 0,in[i] = INT_MAX*1.0;
        FOR(i,1,cnt){
            if(e[i].u != e[i].v && e[i].w < in[e[i].v]){
                in[e[i].v] = e[i].w;
                pre[e[i].v] = e[i].u;
            }
        }
        in[root] = 0;
        FOR(i,1,N){
            ans += in[i];int u;
            for(u = i;u != root && i != vis[u] && !id[u];u = pre[u]) vis[u] = i;
            if(!id[u] && u != root){
                id[u] = ++tot;
                for(int v = pre[u];v != u;v = pre[v]) id[v] = tot;
            }
        }
        if(!tot) return;
        FOR(i,1,N) if(!id[i]) id[i] = ++tot;
        FOR(i,1,cnt){
            double t = in[e[i].v];
            if((e[i].u = id[e[i].u]) != (e[i].v = id[e[i].v])){
                e[i].w -= t;
            }
        }
        N = tot;root = id[root];
    }
}

int main(){
    scanf("%d",&tot);N = 2;
    FOR(i,1,tot){
        scanf("%lf%d",a+N,b+N);
        if(!b[N]) continue;
        add(1,N,a[N]);vis[i] = N++;
    }--N;
    scanf("%d",&M);
    FOR(i,1,M){
        int u,v;double w;
        scanf("%d%d%lf",&u,&v,&w);
        u = vis[u],v = vis[v];
        if(u && v){
            a[v] = std::min(a[v],w);
            e[++cnt] = (Edge){u,v,w};
        }
    }
    FOR(i,2,N){
        //DEBUG(b[i]);DEBUG(a[i]);
        ans += 1.0(b[i]-1)a[i];
    }
    //DEBUG(ans);
    work();
    printf("%.2fn",ans);
    //system("pause");
    return 0;
}