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

于 2011年08月5日 发布在 未分类 跳到评论

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;
}


本文共有 2条评论 | 沙发:文章评论

  1. songtianyi说道:

    我已经快被搞崩溃了,每个人说的都不一样 :cry:

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)