POJ 2987 Firing (构图 最大点权闭合集)

POJ 2987 Firing

题目就不在赘述，很裸的最大点权闭合集，在《最小割模型在信息学竞赛中的应用》有证明，但是呢，我看的不是很懂，今天早上看了一早上，下午又看了一会，还不是很明白，真坑跌，我怎么就理解不了最小割呢？哎，路漫漫，网络流的各种模型我什么时候才能搞懂啊 = =

虽然我不懂，，，但是AC还是没有问题的。。。

 

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
const long long  INF = 2100000000000560ll;
using namespace std;
class Arc{
public:
	int to;
    long long w;
	Arc *next,*anti;
	Arc *ass( int tt,long long ww,Arc* &b ){
		to = tt;w = ww;next = b;b = this;return this;
	}
};
//下面是我的网络流模板，已经A掉无数题了。。。
template<class Tp,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;
    }
    Tp dinic( int u,Tp sum ){
    	Tp 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,Tp 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;
    }
    Tp MaxFlowDinic( int s, int t ){
        S = s;T = t;
        Tp total = 0;
        while( bfs() )
            total += dinic( S,INF );
        return total;
    }
    Tp MaxFlowSap( int s, int t){
        S = s;T = t;
    	int i,md;
        Tp now,total;
    	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;
    }
    //下面是统计闭合集中的点的个数，flag[i]表示i是闭合集中的点
    int check( int u ){
        bool flag[Vsize];
        memset( flag, 0, sizeof(flag) );
        dfs( S,flag );
        return count( flag+1,flag+1+N,true);
    }
    void dfs( int u ,bool *flag){
        flag[u] = true;
        for( Arc *p=biao[u];p != NULL; p = p->next ){
            if(  p->w == 0 || flag[p->to] ) 
                continue; 
            dfs( p->to ,flag);    
        }
    }
};

Network<long long,20010,450000> net;

int main(void){
    int i,N,M,A,B,S,T,W;
    long long po;
    while( scanf("%d%d",&N,&M) != EOF ){
        net.init( N+2 );
        S = N+1; T = N+2;
        po = 0;
        for( i = 1; i <= N; i++ ){
            scanf("%d",&W);
            if( W > 0 ) po += W;
            if( W > 0 ) net.add( S, i, W );
            if( W < 0 ) net.add( i, T, -W);
        }
        while( M-- ){
            scanf("%d%d",&A,&B);
            net.add( A, B, INF );
        }
        po -= net.MaxFlowDinic(S,T);
        printf("%d %lld\n",net.check(S)-1,po);
    }
    return 0;
}