传送门:【POJ】2125 Destroying The Graph
题目分析:要么选择删除一个点的全部入边,要么删除一个点的全部出边,又因为所有的边全部需要被删除,我们可以将本题转化为二分图上的最小点权覆盖,具体建图方法是:将一个点 i 拆成两个点 i ,i',源点向 i 建边,容量为删除该点所有出边的花费,i' 向汇点建边,容量为删除该点所有入边的花费。所有原图上的有向边<u,v>,建边(u,v',INF),因为<u,v'>边容量无穷大,所以我们不可能割这条边,只可能是割和源点直接相连或者和汇点直接相连的边,因此一条边<u,v'>对应的<s,u>,<v',t>一定有一条在割边集中。反证:设最小割后,如果<u,v'>对应的<s,u>,<v',t>都不在割边集中,那么一定有一条增广路通过<s,u>,<u,v'>,<v',t>,那么最小割的容量还可以增加,这和我们设已经是最小割矛盾,得证。
既然知道要么割的是和源点相连的边,要么是和汇点相连的边,那么求一次最小割便能知道割的是那几条边,同时,最小点权覆盖集对应着最小割,最小点权和就是最小割的容量。
如何求是怎么删除的?首先我们从源点沿着残余网络dfs一边,将遇到的点标号。
由于此图是二分图上的网络,所以和源点相连并且没被标号的就是被选择的点(对应删除该点的所有出边这个方案),和汇点相连并且被标号的就是被选择的点(对应删除该点的所有入边这个方案)。
至此,本题解决。
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define REP( i , a , b ) for ( int i = a ; i < b ; ++ i ) #define REV( i , a , b ) for ( int i = a - 1 ; i >= b ; -- i ) #define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define FOV( i , a , b ) for ( int i = a ; i >= b ; -- i ) #define CLR( a , x ) memset ( a , x , sizeof a ) #define CPY( a , x ) memcpy ( a , x , sizeof a ) typedef int type_c ; const int MAXN = 205 ; const int MAXQ = 205 ; const int MAXE = 20005 ; const int INF = 0x3f3f3f3f ; struct Edge { int v , n ; type_c c ; Edge () {} Edge ( int v , type_c c , int n ) : v ( v ) , c ( c ) , n ( n ) {} } ; struct Net { Edge E[MAXE] ; int H[MAXN] , cntE , cntEE ; int d[MAXN] , num[MAXN] , pre[MAXN] , cur[MAXN] ; int Q[MAXQ] , head , tail ; int s ,t , nv ; type_c flow ; int n , m ; bool vis[MAXN] ; int ans[MAXN] ; void init () { cntE = 0 ; CLR ( H , -1 ) ; } void addedge ( int u , int v , type_c c ) { E[cntE] = Edge ( v , c , H[u] ) ; H[u] = cntE ++ ; E[cntE] = Edge ( u , 0 , H[v] ) ; H[v] = cntE ++ ; } void rev_bfs () { CLR ( d , -1 ) ; CLR ( num , 0 ) ; head = tail = 0 ; Q[tail ++] = t ; d[t] = 0 ; num[d[t]] = 1 ; while ( head != tail ) { int u = Q[head ++] ; for ( int i = H[u] ; ~i ; i = E[i].n ) { int v = E[i].v ; if ( ~d[v] ) continue ; d[v] = d[u] + 1 ; num[d[v]] ++ ; Q[tail ++] = v ; } } } type_c ISAP () { CPY ( cur , H ) ; rev_bfs () ; flow = 0 ; int u = pre[s] = s , i , pos , mmin ; while ( d[s] < nv ) { if ( u == t ) { type_c f = INF ; for ( i = s ; i != t ; i = E[cur[i]].v ) if ( f > E[cur[i]].c ) { f = E[cur[i]].c ; pos = i ; } for ( i = s ; i != t ; i = E[cur[i]].v ) { E[cur[i]].c -= f ; E[cur[i] ^ 1].c += f ; } u = pos ; flow += f ; } for ( i = cur[u] ; ~i ; i = E[i].n ) if ( E[i].c && d[u] == d[E[i].v] + 1 ) break ; if ( ~i ) { cur[u] = i ; pre[E[i].v] = u ; u = E[i].v ; } else { if ( 0 == -- num[d[u]] ) break ; mmin = nv ; for ( i = H[u] ; ~i ; i = E[i].n ) if ( E[i].c && mmin > d[E[i].v] ) { mmin = d[E[i].v] ; cur[u] = i ; } d[u] = mmin + 1 ; num[d[u]] ++ ; u = pre[u] ; } } return flow ; } void dfs ( int u ) { vis[u] = 1 ; for ( int i = H[u] ; ~i ; i = E[i].n ) if ( E[i].c && !vis[E[i].v] ) dfs ( E[i].v ) ; } void solve () { int u , v , c ; init () ; s = 0 ; t = 1 ; nv = n * 2 + 2 ; FOR ( i , 1 , n ) { scanf ( "%d" , &c ) ; addedge ( i << 1 | 1 , t , c ) ; } FOR ( i , 1 , n ) { scanf ( "%d" , &c ) ; addedge ( s , i << 1 , c ) ; } REP ( i , 0 , m ) { scanf ( "%d%d" , &u , &v ) ; addedge ( u << 1 , v << 1 | 1 , INF ) ; } printf ( "%d\n" , ISAP () ) ; CLR ( vis , 0 ) ; dfs ( s ) ; int cnt = 0 ; for ( int i = H[s] ; ~i ; i = E[i].n ) if ( !vis[E[i].v] ) ans[cnt ++] = E[i].v ; for ( int i = H[t] ; ~i ; i = E[i].n ) if ( vis[E[i].v] ) ans[cnt ++] = E[i].v ; printf ( "%d\n" , cnt ) ; sort ( ans , ans + cnt ) ; REP ( i , 0 , cnt ) printf ( "%d %c\n" , ans[i] >> 1 , ( ans[i] & 1 ) ? '+' : '-' ) ; } } e ; int main () { while ( ~scanf ( "%d%d" , &e.n , &e.m ) ) e.solve () ; return 0 ; }