ZOJ 3229 Shoot the Bullet (有上下界的最大流 ,ym watashi的题)

于 2011年07月30日 发布在 未分类 跳到评论

ZOJ 3229 Shoot the Bullet 

前几天看了有上下界的各种流,使劲看啊使劲看,终于有点眉目,然后就刷这个题去了。。然后就被虐了= =

之前看书说是求最大流的时候需要二分下界看是否有可行流,但是,我想来想去,这尼玛坑爹啊,怎么都会超时的,但是试了各种二分,dinic,sap都用了,就是超时,感觉一定有什么不对劲,放那里,过两天再看。。

今天小媛赐予我《新编实用算法与程序设计》,俗称蓝书,看了看二分图部分后,就顺便看了看网络流的部分,里面有讲这个,我仔细看了看,终于理解了求可行流时候为什么要那样构图,而且发现其实不用二分下界,只需要删掉T->S的弧,然后求个S,T的最大流就行了。。因为下界(必满,已经在求可行流时候满足了)没有包含在残量网络里,所以直接扩流就行了  = =。。。

对于本题,因为有些奇怪的单词,可能读题比较困难,n天给m个mm拍照,每个mm有拍照数量下限,每天有拍照数量的上界,每天拍照某个mm也有数量限制,求这n天能拍到的最多的mm数,和每天拍的数量。建图很弱啦。。。。代码木有注释,。。。凑活着看吧。。。=  =


#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;
const int MAXN = 365+1000+4;
const int inf = 99999999;

class Arc{
public:
    int to,w;
    int l,r;
    Arc *next,*anti;
    Arc *add( int tt,int ll,int rr,Arc *&b ){
        to = tt; l = ll; r = rr;
        w = rr-ll;next = b;b = this; return this;
    }
};

int d[ MAXN ],S,T,bound,countt,in[ MAXN ],out[ MAXN ];
Arc a[ MAXN *80 ],*biao[ MAXN ];

void init( int n ){
    bound = n;S = n - 2;T = n - 1;
    for( int i = 0; i < n; i++ )
        biao[i] = NULL;
    memset( in, 0, sizeof(in) );
    memset( out, 0, sizeof(out) );
    countt = 0;
}

void add( int from,int to, int l,int r ){
    Arc *p1 = a[ countt++ ].add( to, l, r, biao[from] );
    Arc *p2 = a[ countt++ ].add( from, 0, 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 = sum;
    if( u == T ) return 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 max_flow1( void ){
    int total = 0;
    while( bfs() )
        total += dinic( S, 2100000000 );
    return total;
}

int max_flow(){
	int i,now_flow,total,min_dist;
	Arc *ge[MAXN],*di[MAXN],*path[MAXN];
	int dist[MAXN],countdist[MAXN],his[MAXN],pre[MAXN],n=bound;
	Arc *p,*locate;
	bool flag;
	memset( dist,0,sizeof(dist) );
	memset( countdist,0,sizeof( countdist) );
	countdist[0] = n;
	for( i = 0; i < n ; i++ ) di[i] = ge[i] = biao[i];
	for( total = 0, now_flow = inf,i = S; dist[i] < n; ){
		his[i] = now_flow;
		for( flag = false,p=di[i]; p!=NULL; p= p->next){
			if( p->w > 0 && dist[i] ==dist[p->to] + 1 ){
				now_flow = min( now_flow,p->w );
				pre[ p->to ] = i;
				path[ p->to ] = p;
				di[i] = p;
				i = p->to;
				if( i == T ){
					for( total += now_flow; i != S; i = pre[i] )
						path[i]->w -= now_flow, path[i]->anti->w += now_flow;
					now_flow = inf;
				}
				flag = true;
				break;
			}
		}
		if( !flag ){
			for( min_dist = n-1,p=ge[i];p!= NULL;p=p->next )
				if( p->w > 0 && dist[p->to] < min_dist )
					min_dist = dist[p->to],locate = p;
			di[i] = locate;
			if( !(--countdist[ dist[i] ] ) ) break;
			countdist[ dist[i] = min_dist+1 ] ++;
			if( i != S )
				i = pre[i],now_flow = his[i];

		}
	}
	return total;
}

void construct( void ){
    for( int i = 0; i < bound - 2; i++ )
        for( Arc *p=biao[i]; p!=NULL; p = p->next ){
            in[ p->to ] += p->l;
            out[ i ] += p->l;
        }
    for( int i = 0; i < bound - 2; i++ ){
            add( S, i, 0, in[i]  );
            add( i, T, 0, out[i] );
    }
}

bool full( void ){
    for( Arc *p = biao[S]; p != NULL; p = p->next )
        if( p->w > 0 ) return false;
    return true;
}

int main(void){
    int n,m,from,to;
    int i,j,c,d,r,l;
    while( scanf("%d%d",&n,&m) != EOF ){
        init(n+m+4);
        for( i = 0; i < m; i++ ){
            scanf("%d",&j);
            add( n+i, n+m+1, j, inf );
        }
        queue<int> q;
        for( i = 0; i < n; i++ ){
            scanf("%d%d",&c,&d);
            add( n+m, i, 0, d );
            while( c-- ){
                scanf("%d%d%d",&j,&r,&l);
                q.push( countt );
                add( i, n+j, r, l );
            }
        }
        j = countt;
        add( n+m+1, n+m, 0, inf );
        construct();
        max_flow();

        if( !full() ){
            puts("-1\n");continue;
        }
        a[j].w = a[j+1].w = 0;
        S = n+m;T = S+1;
        max_flow1();
        int total = 0;
        for( Arc *p = biao[S]; p != NULL; p = p->next )
            if( p->to >= 0 && p->to < n ) {
                total += p->r - p->w;
            }
        printf("%d\n",total);
        while( !q.empty() ){
            int u = q.front();q.pop();
            printf("%d\n",a[u].r - a[u].w );
        }
        printf("\n");
    }
    return 0;
}

一个max_flow是sap,一个max_flow1是dinic,都能过,这个题就可以作为我的模板了。。。
网络流以后应该向建图方面发展了,知识性的东西在以后做题过程中巩固吧。。

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

  1. dianbei说道:

    你好,我这题也一直tle,看了您的题解后才知道不用二分。。。。。 顺利AC,灰常感谢! :mrgreen:

留下评论!

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