hdu 2121

朱刘算法求无根最小树形图

可以任意选一个根，求最小的权和以及当时的根。

先建一个超级根，它连向所有点，边权为所有边的边权和加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" );

     }

 }