POJ 1149 PIGS (建图搞死人= =）

POJ 1149 PIGS

以前刚开始看网络流的时候，下载过一个文档，《网络流建模汇总 by Edelweiss》，里面第一个模型就是这个题，当时看了好长时间，没看懂= =b，这两天重新看过之后，思路清晰了许多。网络流难的不是dinic，sap呀什么的，是建图，搞死人呢。。。

经过一番搜题解之后，我发现最详细的解释出自这里，凑活着看吧，上面的文档中也有（不过我打印出来是黑白的，图示不清）。

我就不多说了（= =b，是不是很不厚道）。以下代码是我1Y的，用class封装的dinic，现在用着已经很爽了，用virtual judge交的时候还跑了个0ms。

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
const int maxn = 110;
const int maxm = 1010;
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;
	}
};
class Network{
public:
    Arc a[ 5000 ],*biao[ maxn ];
    int countt,total,d[maxn],S,T;
    Network(void) {}
    Network( int n ) {init(n) ;}
    
    void init( int n ){
        countt = 0;
        for( int i = 0; i < n; i++ )
            biao[i] = NULL;
        S = n - 2;T = n - 1;
    }
    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 bfs( void ){
    	queue<int> q;
    	fill( d,d+maxn,-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;
    }
    int maxflow( int s, int t ){
        S = s;T = t;
        int total = 0;
        while( bfs() )
            total += dinic(S,inf );
        return total;
    }
};

int N,M,A,B;
int has[ maxm ];
int buy[ maxn ];
int main(void){
    int i,j,k;
    while( scanf("%d%d",&M,&N) != EOF ){
        Network net( N + 3 );
        vector<int> V[maxm];
        for( i = 1; i <= M; i++ )
            scanf("%d",&has[i] );
        for( i = 1; i <= N; i++ ){
            scanf("%d",&A);
            while( A-- ){
                scanf("%d",&j);
                V[j].push_back(i);
            }
            scanf("%d",&buy[i]);
        }
        for( i = 1; i <= M; i++ ){
            if( V[i].size() == 0 ) continue;
            net.add( net.S, V[i][0], has[i] );
            for( j = 1; j < V[i].size(); j++ )
                net.add( V[i][j-1], V[i][j], inf );
        }
        for( i = 1; i <= N; i++ )
            net.add( i, net.T, buy[i]);
        printf("%d\n", net.maxflow(net.S,net.T) );
    }
    return 0;
}