Luogu P4716 【模板】最小树形图

题目链接\(Click\) \(Here\)

不知道有什么用的一个东西。本来不打算再大量扩知识点了但还是学一下好了，反正也不难。

原理：树上父亲唯一，每次选最短的父边。

此时会有两类情况：

就这样正常连下去，这样我们就得到了一个尽可能小的树形图。

成环。这种情况下我们需要拆掉环里的一条边换成其他的边。

我们记录一下到达每个点的最短父边权值是多少。对于成环的情况，可以先把环里面所有边的权值选上，把环里面的所有点看成一个。然后等到有其它外来的边连进来的时候，再选一个最小的外来边，去掉环里面原先所暂时使用的边，换成外来的那个，就这样一直求解直到不再有环。

#include<bits/stdc++.h>usingnamespace std;typedeflonglong ll;constint N =100+5;constint M =10000+5;const ll INF =0x3f3f3f3f;int n, m, r;struct edge {int u, v, w;} e[M];int fa[N], id[N], top[N], minw[N];ll get_ans (int n,int m){ll ans =0;while(true){int cnt =0;for(int i =1; i <= n;++i){id[i]= top[i]=0; minw[i]= INF;}for(int i =0; i < m;++i){if(e[i].u != e[i].v && e[i].w <minw[e[i].v]){ fa[e[i].v]= e[i].u;minw[e[i].v]= e[i].w;}} minw[r]=0;for(int i =1; i <= n;++i){if(minw[i]== INF)return–1; ans += minw[i];int u = i;while(u != r && top[u]!=i&&!id[u]){top[u]= i; u = fa[u];}if(u != r &&!id[u]){ id[u]=++cnt;for(int v = fa[u]; v != u; v = fa[v]) id[v]= cnt;}}if(cnt ==0)return ans;for(int i =1; i <= n;++i){if(!id[i])id[i]=++cnt;}for(int i =0; i < m;++i){int prew = minw[e[i].v]; e[i].u = id[e[i].u]; e[i].v = id[e[i].v];if(e[i].u != e[i].v){e[i].w -= prew;}}n = cnt; r = id[r];}}int main (){cin>> n >> m >> r;for(int i =0; i < m;++i){staticint u, v, w; cin >> u >> v >> w;e[i]=(edge){u, v, w};}cout << get_ans (n, m)<< endl;}

以及非常感谢 @旋转卡壳 的代码。仅仅是读注释就可以快速理解整个算法的流程。（虽然代码不加空格\(www\)）