最小树形图

求最短弧集合 \(E\)
找到每个 \(u\) 点的最小入边 \(in[u]\) ，如果存在非根节点没有入边，则一定不存在树形图

for(ri int i=1;i<=m;++i){
    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;
    }
}
for(ri int i=1;i<=n;++i) if(i^rt&&!pre[i]) return -1;

判断集合 \(E\) 中有没有有向环，如果有转步骤 \(3\) ，否则转 \(4\)
一定要记录 \(cnt\) 或开一个 \(bool\) 数组记录走过的边，不然可能疯狂走环；

cnt=in[rt]=0; 
		for(ri int i=1,v;i<=n;++i){
    as+=in[v=i];
    while(vs[v]^i&&!id[v]&&v^rt) vs[v]=i,v=pre[v];
    if(!id[v]&&v^rt){
        id[v]=++cnt,v=pre[v];
        while(!id[v]) id[v]=cnt,v=pre[v];
    }            
}
if(!cnt) break;

收缩点，把有向环收缩成一个点，并且对图重新构建，包括边权值的改变和点的处理，之后再转步骤 \(1\)
对于环外指向环的边 \((u \to v, w)\) ，其边权变为 \(w-in[v]\)

for(ri int i=1;i<=n;++i) if(!id[i]) id[i]=++cnt;
for(ri int i=1;i<=m;++i){
    if(id[e[i].u]^id[e[i].v]) e[i].w-=in[e[i].v];
    e[i].u=id[e[i].u],e[i].v=id[e[i].v];
} 
rt=id[rt],n=cnt;

展开收缩点，求得最小树形图
如果不需要输出具体方案，直接返回 \(ans\) 即可

code

#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;

namespace Q{
    il int rd(){
        ri int x=0;ri bool f=0;ri char c=getchar();
        while(c^EOF&&!isdigit(c)) f|=(c==45),c=getchar();
        while(c^EOF&&isdigit(c)) x=x*10+(c^48),c=getchar();
        return f?-x:x;
    }
    il void wt(int x){
        if(x<0) x=-x,putchar(45);
        if(x>=10) wt(x/10);
        return putchar(x%10|48),void();
    }
} using namespace Q;

cs int N=105,M=10004,inf=1<<30;
int in[N],pre[N],id[N],n,m,rt,vs[N];
struct qwq{int u,v,w;}e[M];

il int calc(){
    ri int as=0,cnt=0;
    while(1){
        for(ri int i=1;i<=n;++i) in[i]=inf,pre[i]=vs[i]=id[i]=0;
        for(ri int i=1;i<=m;++i){
            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;
            }
        }
        for(ri int i=1;i<=n;++i) if(i^rt&&!pre[i]) return -1;
        cnt=in[rt]=0; 
		for(ri int i=1,v;i<=n;++i){
            as+=in[v=i];
            while(vs[v]^i&&!id[v]&&v^rt) vs[v]=i,v=pre[v];
            if(!id[v]&&v^rt){
                id[v]=++cnt,v=pre[v];
                while(!id[v]) id[v]=cnt,v=pre[v];
            }            
        }
        if(!cnt) break;
        for(ri int i=1;i<=n;++i) if(!id[i]) id[i]=++cnt;
        for(ri int i=1;i<=m;++i){
            if(id[e[i].u]^id[e[i].v]) e[i].w-=in[e[i].v];
            e[i].u=id[e[i].u],e[i].v=id[e[i].v];
        } 
        rt=id[rt],n=cnt;
    }
    return as;
}

signed main(){
    n=rd(),m=rd(),rt=rd();
    for(ri int i=1;i<=m;++i){
        e[i].u=rd(),e[i].v=rd(),e[i].w=rd();
    }
    wt(calc());
    return 0;
}

526互联

最小树形图

最小树形图