SGU 242 Student’s Morning (有上下界的可行流)

SGU 242 Student’s Morning

学生要去学校游玩，每个学生有几个喜欢的学校，要求每个学校至少有两个人，我们可以这样建图，从学校到学生建立[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&&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;
    }

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