前几天看了有上下界的各种流,使劲看啊使劲看,终于有点眉目,然后就刷这个题去了。。然后就被虐了= =
之前看书说是求最大流的时候需要二分下界看是否有可行流,但是,我想来想去,这尼玛坑爹啊,怎么都会超时的,但是试了各种二分,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,都能过,这个题就可以作为我的模板了。。。
网络流以后应该向建图方面发展了,知识性的东西在以后做题过程中巩固吧。。
你好,我这题也一直tle,看了您的题解后才知道不用二分。。。。。 顺利AC,灰常感谢!
难得有人来这里转转。。。。
请问您的dinic和sap的运行时间分别是多少?我一直写的是dinic,不知道sap的效率如何。
click here
200ms左右是sap,1s以上的是一次用dinic,一次用sap,如果两个都用dinic。。会超时。。
看到这么神的效率,我也忍不住写了个sap版,结果1s6过。。。我太弱了。
加优化了没?什么gap什么的。。
有加的,后来我在连边方面优化了一下,刷到300ms内。