问题描述
给定一张无向图和一个根r，求出一个n-1条边的一张子图，使得从r出发可以到达任意一个点，同时使得所有选择的边权之和最小。
根据最小树形图的定义，这张图的除了根的每一个点都必须有且仅有一个入度。
那么我们可以贪心一点，对于除了根的所有点都找出一条连向它的边且边权最小，称作这个点的代表边，并把这些边权加入答案中。
然后我们找出了一张图，这张图中每个点都只有一个入度。
如果不算根的话，它应当是一个外向基环树森林。
然后我们找到所有的环，把它们缩成一个点。
再去扫描不在环内的边，假设有u->v,那么这条边的边权要减掉v的代表边权。
因为v是一个环，如果继续连u->v的边的话，相当于是把原来v的父亲断开，再连上u。
于是我们就完成了缩点，一直做下去，知道图中没有环。
无解就是图中除了根有点没有入度。
代码细节
1、初始化，我们令id[]表示这个点在那个环里，top[]表示环顶(找环时用)，mi[]表示代表边的边权,cnt表示环数。
2、找环的时候，因为是一颗外向基环树，所以我们对于每个点记录father，这样father就变成了内向基环树，这样可以方便找环。
3、没有和其他点组成环的让它自己成为一个环。
4、每做完一轮之后要更新一下点数和根。
代码
#include<iostream> #include<cstdio> #define N 109 #define M 10009 #define inf 2e9 using namespace std; int tot,top[N],id[N],cnt,mi[N],n,m,fa[N],r; long long ans; inline int rd(){ int x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } struct edge{int from,to,l;}e[M]; inline void add(int u,int v,int l){e[++tot].to=v;e[tot].l=l;e[tot].from=u;} inline bool solve(){ while(1){ for(int i=1;i<=n;++i)id[i]=top[i]=0,mi[i]=inf; for(int i=1;i<=m;++i) if(e[i].to!=e[i].from&&e[i].l<mi[e[i].to]) fa[e[i].to]=e[i].from,mi[e[i].to]=e[i].l; int u=0;mi[r]=0; for(int i=1;i<=n;++i){ if(mi[i]==inf)return 0; ans+=mi[i]; for(u=i;u!=r&&top[u]!=i&&!id[u];u=fa[u])top[u]=i; if(u!=r&&!id[u]){ id[u]=++cnt; for(int v=fa[u];v!=u;v=fa[v])id[v]=cnt; } } if(!cnt)return 1; for(int i=1;i<=n;++i)if(!id[i])id[i]=++cnt; for(int i=1;i<=m;++i){ int num=mi[e[i].to]; e[i].from=id[e[i].from];e[i].to=id[e[i].to]; if(e[i].from!=e[i].to)e[i].l-=num; } n=cnt;r=id[r];cnt=0; } } int main(){ n=rd();m=rd();r=rd();int u,v,w; for(int i=1;i<=m;++i){ u=rd();v=rd();w=rd();add(u,v,w); } if(solve())cout<<ans; else puts("-1"); return 0; }