hdu 3435 图回路分割

将一个无向图分成许多回路，回路点交集为空，点幷集为V。幷最小化回路边权和。

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <vector>

 #define maxn 2010

 #define oo 0x3f3f3f3f

 using namespace std;

 struct Edge {

     int u, v, c, f;

     Edge( int u, int v, int c, int f ):u(u),v(v),c(c),f(f){}

 };

 struct Mcmf {

     int n, src, dst;

     vector<Edge> edge;

     vector<int> g[maxn];

     int dis[maxn], pth[maxn], ext[maxn];

     void init( int n, int src, int dst ) {

         this->n = n;

         this->src = src;

         this->dst = dst;

         for( int u=; u<=n; u++ )

             g[u].clear();

         edge.clear();

     }

     void add_edge( int u, int v, int c, int f ) {

         g[u].push_back( edge.size() );

         edge.push_back( Edge(u,v,c,f) );

         g[v].push_back( edge.size() );

         edge.push_back( Edge(v,u,-c,) );

     }

     bool spfa( int &flow, int &cost ) {

         queue<int> qu;

         memset( dis, 0x3f, sizeof(dis) );

         qu.push( src );

         dis[src] = ;

         pth[src] = -;

         ext[src] = true;

         while( !qu.empty() ) {

             int u=qu.front();

             qu.pop();

             ext[u] = false;

             for( int t=; t<g[u].size(); t++ ) {

                 Edge &e = edge[g[u][t]];

                 if( e.f && dis[e.v]>dis[e.u]+e.c ) {

                     dis[e.v] = dis[e.u]+e.c;

                     pth[e.v] = g[u][t];

                     if( !ext[e.v] ) {

                         ext[e.v] = true;

                         qu.push( e.v );

                     }

                 }

             }

         }

         if( dis[dst]==oo ) return false;

         int flw = oo;

         for( int eid=pth[dst]; eid!=-; eid=pth[edge[eid].u] )

             flw = min( flw, edge[eid].f );

         for( int eid=pth[dst]; eid!=-; eid=pth[edge[eid].u] ) {

             edge[eid].f -= flw;

             edge[eid^].f += flw;

         }

         flow += flw;

         cost += flw*dis[dst];

         return true;

     }

     bool mcmf( int &flow, int &cost ) {

         flow = cost = ;

         while(spfa(flow,cost));

         return true;

     }

 };

 int n, m;

 Mcmf M;

 int main() {

     int T;

     scanf( "%d", &T );

     for( int cas=; cas<=T; cas++ ) {

         printf( "Case %d: ", cas );

         scanf( "%d%d", &n, &m );

         M.init( n+n+, n+n+, n+n+ );

         for( int i=,u,v,w; i<=m; i++ ) {

             scanf( "%d%d%d", &u, &v, &w );

             M.add_edge( u, v+n, w,  );

             M.add_edge( v, u+n, w,  );

         }

         for( int u=; u<=n; u++ ) {

             M.add_edge( M.src, u, ,  );

             M.add_edge( u+n, M.dst, ,  );

         }

         int flow, cost;

         M.mcmf( flow, cost );

         if( flow!=n ) printf( "NO\n" );

         else printf( "%d\n", cost );

     }

 }