学生要去学校游玩,每个学生有几个喜欢的学校,要求每个学校至少有两个人,我们可以这样建图,从学校到学生建立[0,1]的弧,从学生到汇点T,建立[0,1]的弧,对于每个学校从源点建立下界为2的弧,从T到S建立[0,2*K]的路,这样就可以用模板了。今天晚上来到实验室,完全手写的代码,竟然一次AC了,十分高兴,而且代码也些的很工整,用作网络流的模板啦~
#include<iostream> #include<cstdio> #include<queue> #include<algorithm> #include<cstring> const int MAX = 200 + 200 + 4 + 1 ; const int inf = 999999999; using namespace std; class Arc{ public: int to,w; int l,r; Arc *next,*anti; Arc *ass( int tt,int ll,int rr,Arc *&b ){ to = tt; l = ll; r = rr; w = r - l;next = b; b = this; return this; } }; class Network{ public: int d[ MAX ],S,T,countt,N; int in[ MAX ],out[ MAX ]; Arc a[ MAX * 100 ],*biao[ MAX ]; Network( void ) {} Network( int n ) { init(n); } void init(int n){ N = n;//最多的点数。。。 for( int i = 1; i <= N; i++ ) biao[i] = NULL; countt = 0; } void add( int from,int to, int l,int r ){ Arc *p1 = a[ countt++ ].ass( to, l, r, biao[from] ); Arc *p2 = a[ countt++ ].ass( from, 0, 0, biao[to] ); p1->anti = p2; p2->anti = p1; } int bfs( void ){ queue<int> q; fill( d, d+MAX, -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&∑ 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; } void construct( void ){ for( int i = 1; i <= N - 2; i++ ) for( Arc *p = biao[i]; p != NULL; p = p->next ){ if( !p->l && !p->r ) continue; in[ p->to ] += p->l; out[ i ] += p->l; } for( int i = 1; i <= N - 2; i++ ){ if( in[i] > out[i] ) add( N - 1, i, 0, in[i] - out[i] ); if( in[i] < out[i] ) add( i, N, 0, out[i] - in[i]); } } bool full( void ){ for( Arc *p = biao[N-1]; p != NULL; p = p->next ) if( p->w ) return false; return true; } }; int main(void){ int S,T,outstart; int N,K; int i,j,k; while( scanf("%d%d",&N,&K) != EOF ){ S = N + K + 1; T = N + K + 2; Network net( T + 2 ); for( i = 1; i <= N; i++ ){ net.add( K + i, T, 0, 1 ); scanf("%d",&j); while( j-- ){ scanf("%d",&k); net.add( k, K + i, 0, 1 ); } } outstart = net.countt; for( i = 1; i <= K; i++ ) net.add( S, i, 2, N ); net.add( T, S, 2*K, N ); net.construct(); net.maxflow(S+2,T+2); if( !net.full() ){ puts( "NO" );continue; } puts( "YES" ); for( i = 1; i <= K; i++ ){ printf("%d",net.a[ outstart + (i - 1)*2 ].r - net.a[ outstart + (i - 1)*2 ].w ); for( Arc *p=net.biao[i]; p != NULL; p=p->next ) if( p->w == 0 && p->to > K && p->to <= K+N ){ printf(" %d",p->to - K ); } puts( "" ); } } return 0; }