朱刘算法求无根最小树形图
可以任意选一个根，求最小的权和以及当时的根。
先建一个超级根，它连向所有点，边权为所有边的边权和加1（即sumw+1），然后求以它为根的最小树形图，再根据树形图权和与2*(sumw+1)的关系判断是否存在解（如果大于等于就不存在，否则存在）。
至于求对应的原图中的根，我们发现自始自终，超级根都不可能在一个环中，并且在最有一个状态，一定是一个没有环的树形图，该图中与前趋为超级根的点，就是原图中的根所在的环缩成的点，怎么得到具体是哪一个点呢，我们可以记下那条边在最开始指向的是哪个点，那个点就是原图中的根（可以根据缩点的正确性证明它的正确性）。
#include <cstdio>
#define oo 0x7FFFFFFF
#define N 1010
#define M 11010 struct Edge {
int u, v, w;
int sv;
Edge(){}
Edge( int u, int v, int w ):u(u),v(v),w(w),sv(v){}
}; int n, m;
int inw[N], inc[N], pre[N], idx[N], vis[N], rsv;
Edge edge[M]; int directed_mst( int root ) {
int rt = ;
while() {
// inw pre
for( int i=; i<=n; i++ )
inw[i] = oo;
for( int i=; i<=m; i++ ) {
Edge &e = edge[i];
if( inw[e.v]>e.w ) {
inw[e.v]=e.w;
pre[e.v]=e.u;
if( e.u==root ) rsv=e.sv;
}
}
// inc idx
int cnt = ;
for( int i=; i<=n; i++ )
idx[i] = vis[i] = ;
for( int i=,u,v; i<=n; i++ ) {
if( i==root ) continue;
for( u=pre[i]; u!=root && !idx[u] && vis[u]!=i; u=pre[u] )
vis[u]=i;
if( u==root || idx[u] ) continue;
cnt++;
for( v=pre[u]; v!=u; v=pre[v] ) {
idx[v] = cnt;
inc[v] = true;
rt += inw[v];
}
idx[u] = cnt;
inc[u] = true;
rt += inw[u];
}
if( cnt== ) {
for( int i=; i<=n; i++ )
if( i!=root )
rt += inw[i];
break;
} else {
for( int i=; i<=n; i++ )
if( !idx[i] ) {
idx[i] = ++cnt;
inc[i] = false;
}
}
// edge
int j=;
for( int i=; i<=m; i++ ) {
Edge &e = edge[i];
if( inc[e.v] ) e.w-=inw[e.v];
e.u = idx[e.u];
e.v = idx[e.v];
if( e.u!=e.v ) edge[++j]=edge[i];
}
root = idx[root];
n = cnt;
m = j;
}
return rt;
} int main() {
while( scanf("%d%d",&n,&m)== ) {
int mm=, sw=;
for( int i=,u,v,w; i<=m; i++ ) {
scanf( "%d%d%d", &u, &v, &w );
if( u==v ) continue;
u++, v++;
edge[++mm] = Edge(u,v,w);
sw+=w;
}
for( int i=; i<=n; i++ )
edge[++mm] = Edge(n+,i,sw+);
m = mm;
n = n+;
int ans = directed_mst(n)-sw-;
if( ans>=sw+ ) printf( "impossible\n" );
else printf( "%d %d\n", ans, rsv- );
printf( "\n" );
}
}