POJ 2125 Destroying The Graph (最大点权覆盖集)

POJ 2125  Destroying The Graph

破坏一个棵树的，就是把他的所有边都删掉，现在有两种方式就是删掉i点的所有入边，还有就是删掉i点的所有出边，所需要的费用为Wi+，Wi-,每一条边<u,v>要被销掉，要么删除u的所有出边，要么删除v的所有入边，每条边都至少与一种操作相关联，我们可以联想到二分图的最小点集覆盖，求最小的点集，让所有的边都与之关联。对于这个题来说就是典型的模型了。二分图的最小点权覆盖，AMBER的论文第30页有讲，不再赘述，注意不要把边权选错了，入度的权在右边。。。我因为这个搞了一个下午。

还有，我的最大流模板已经十分完善了，就在blog上放我的模板，以后会填上费用流，强连通等的并且不断改进：

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
const int INF = 2100000000;
using namespace std;
class Arc{
public:
	int to,w;
	Arc *next,*anti;
	Arc *ass( int tt,int ww,Arc* &b ){
		to = tt;w = ww;next = b;b = this;return this;
	}
};
template< int Vsize, int Esize >
class Network{
private:
    Arc A[ 2*Esize+10 ],*biao[ Vsize ];
    int countt,d[ Vsize ],S,T,N;

    int bfs( void ){
    	queue<int> q;
    	fill( d,d+Vsize,-1 );
    	d[ S ] = 0;
    	q.push( S );
    	while( !q.empty() ){
    		int u = q.front();q.pop();
    		for(Arc *p=biao[u];p!=NULL;p=p->next)
    			if( d[p->to] == -1 && p->w > 0 )
    				d[p->to] = d[u]+1,q.push(p->to);
    	}
    	return d[T] != -1;
    }
    int dinic( int u,int sum ){
    	int f,o;
    	if( u == T ) return sum;
    	o = sum;
    	for(Arc*p=biao[u];p!=NULL&&sum;p=p->next)
    		if( d[p->to] == d[u]+1 && p->w > 0 ){
    			f = dinic(p->to,min(p->w,sum));
    			p->w -= f;p->anti->w += f;
    			sum -= f;
    		}
    	return o-sum;
    }
public:
    Network( void ) {}
    Network( int n ) { init(n) ;}

    void init( int n ){
        countt = 0;N = n;
        for( int i = 0; i <= n; i++ )
            biao[i] = NULL;
    }
    void add( int from,int to,int w ){
    	Arc *p1 = A[countt++].ass( to,w ,biao[from]);
    	Arc *p2 = A[countt++].ass( from,0,biao[ to] );
    	p1->anti = p2; p2->anti = p1;
    }
    int MaxFlowDinic( int s, int t ){
        S = s;T = t;
        int total = 0;
        while( bfs() )
            total += dinic( S,INF );
        return total;
    }
    int MaxFlowSap( int s, int t){
        S = s;T = t;
    	int i,now,total,md;
    	Arc *p,*locate,*ge[ Vsize ],*di[ Vsize ],*path[ Vsize ];
    	int dist[ Vsize ], cd[  Vsize ];
        int his[  Vsize ], pre[ Vsize ];;
    	bool flag;
    	memset( dist,0, sizeof(dist) );
    	memset( cd,  0, sizeof(cd)   );
    	cd[0] = N;
    	for( i = 0; i <= N ; i++ )
            di[i] = ge[i] = biao[i];
    	for( total = 0, now = INF,i = S; dist[i] < N; ){
    		his[i] = now;
    		for( flag = false,p=di[i]; p!=NULL; p= p->next){
    			if( p->w > 0 && dist[i] ==dist[p->to] + 1 ){
    				now = min( now,p->w );
    				pre[ p->to ] = i;
    				path[ p->to ] = p;
    				di[i] = p;
    				i = p->to;
    				if( i == T ){
    					for( total += now; i != S; i = pre[i] )
    						path[i]->w -= now, path[i]->anti->w += now;
    					now = INF;
    				}
    				flag = true;
    				break;
    			}
    		}
    		if( !flag ){
    			for( md = N-1,p=ge[i];p!= NULL;p=p->next )
    				if( p->w > 0 && dist[p->to] < md )
    					md = dist[p->to],locate = p;
    			di[i] = locate;
    			if( !(--cd[ dist[i] ] ) ) break;
    			cd[ dist[i] = md+1 ] ++;
    			if( i != S )
    				i = pre[i],now = his[i];
    		}
    	}
    	return total;
    }

    void check( int t ){
        vector<int> V;int i;
        bool flag[Vsize];
        memset( flag, 0, sizeof(flag) );
        dfs( S, flag );
        for(Arc *p = biao[S]; p != NULL; p = p->next )
            if(  !flag[p->to] ) V.push_back( p->to );
        for(Arc *p = biao[T]; p != NULL; p = p->next )
            if(  flag[p->to] ) V.push_back( -p->to );
        printf("%d\n", V.size() );
        for( i = 0; i < V.size(); i++ ){
            if( V[i] > 0 ) printf("%d -\n",V[i] );
            if( V[i] < 0 ) printf("%d +\n",-V[i]-t);
        }
    }
    void dfs( int u , bool *flag ){
        flag[u] = true;
        for(Arc *p = biao[u]; p != NULL; p = p->next ){
            if( flag[p->to] || p->w == 0 ) continue;
            dfs( p->to, flag );
        }
    }
};

Network<210,7000> net;

int main(void){
    int N,M,from,to,i,j,k;
    int S,T,cases;
    scanf("%d",&cases);
    while( cases-- ){
        scanf("%d%d",&N,&M);
        net.init( N*2+2 );
        S = N*2 + 1;
        T = N*2 + 2;
        for( i = 1; i <= N; i++ ){
            scanf("%d",&j);
            net.add( N+i, T, j);
        }
        for( i = 1; i <= N; i++ ){
            scanf("%d",&j);
            net.add( S, i, j );
        }
        while( M-- ){
            scanf("%d%d",&from,&to);
            net.add( from ,N+to, INF );
        }
        printf("%d\n",net.MaxFlowSap(S,T) );
        net.check(N);
        if( cases ) printf("\n");
    }
    return 0;
}