很裸地无源汇的可行流,我看了看论文但是不是很明白他的工作原理,虽然A了,但是心里没底。。
纯粹留下代码,方便以后用。。
#include<string> #include<cstdlib> #include<cstdio> #include<queue> #include<algorithm> #include<iostream> using namespace std; const int maxn = 210; class Arc{ public: int to,w; int cap,low; Arc *next,*anti; Arc *ass( int tt,int cc,int ll,int ww,Arc* &b ){ to=tt;cap=cc;low=ll;next=b;b=this; w = ww; return this; } } a[ maxn*maxn ],*biao[ maxn ]; int countt,d[ maxn ],S,T,N,M; int inlbsum[ maxn ]; int outlbsum[ maxn ]; void add( int from,int to,int lb,int cap ){ outlbsum[from] += lb; inlbsum[to] += lb; Arc *p1 = a[ countt++ ].ass(to,cap,lb,cap-lb,biao[from]); Arc *p2 = a[ countt++ ].ass(from,0,0,0,biao[to]); p1->anti = p2; p2->anti = p1; } int bfs( void ){ queue<int> q; fill( d+1,d+1+N+2,-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; 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; } bool full( void ){ for( Arc *p = biao[S]; p != NULL; p = p->next ) if( p->w ) return false; return true; } int main(void){ int i,j,cases; int from,to,lb,cap; scanf("%d",&cases); while( cases-- ){ scanf("%d%d",&N,&M); S = N+1; T = N+2; for( i = 1; i <= N+2; i++ ) biao[i] = NULL,inlbsum[i]=outlbsum[i]=0; countt = 0; for( i = 0; i < M; i++ ){ scanf("%d%d%d%d",&from,&to,&lb,&cap); add(from,to,lb,cap); } for( i = 1; i <= N; i++ ){ if( inlbsum[i] > outlbsum[i] ) add( S,i,0,inlbsum[i]-outlbsum[i] ); if( outlbsum[i] > inlbsum[i] ) add( i,T,0,outlbsum[i]-inlbsum[i] ); } int total = 0; while( bfs() ) total += dinic(S,2100000000); if( full() ) { printf("YES\n"); } else{ printf("NO\n"); if( cases ) puts(""); continue; } for( i = 0; i < 2*M; i += 2 ) printf("%d\n",a[i].cap - a[i].w); if( cases ) cout<< endl; } return 0; }