Poj Solution 3189

http://poj.org/problem?id=3189

#include <vector>
#define min(a,b) (((a)<(b))?(a):(b))

using namespace std;

class ff
{

public:    
    typedef int type;            // ��Ȩ����
    enum { size = 1110 };        // �����ģ
    enum { max = ( 1<<30 ) };    // �����������

    //    ��ʼ��
    void init();

    //    ����һ��� from �� to ��������Ϊ limit �������
    void insert_edge( int from, int to, type limit );

    //    ����n����ͼ�У��� ����s �� ����t �������
    type maxflow( int n, int s, int t );

private:

    struct edge
    {
        int to;        // �ñ�ָ��Ķ�
        type c, f;  // ��������
        int rev_i;  // e[to][rev_i] Ϊ�ñߵ������
    };//�ߵ�����

    typedef vector<edge> set_edge;  // �ߵļ�������

    set_edge e[size]; // ��
    bool sign[size];  // ���ʱ�־
    
    void add_flow( edge &ee, type d );        // ��ӱߵ���
    type search( int k, int t, int best );  // ��������ع첢����
};

/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
//    ������


void ff::init()
{
    int i;
    for( i=0; i<size; i++ )
        e[i].clear();
}
void ff::insert_edge( int from, int to, type limit )
{
    edge e1 = { to, limit, 0, e[to].size() }, e2 = { from, 0, 0, e[from].size() };

    e[ from ].push_back( e1 );
    e[ to ].push_back( e2 );
}

void ff::add_flow( edge &ee, type d )
{
    ee.f += d;
    e[ ee.to ][ ee.rev_i ].f -= d;
}

ff::type ff::search( int k, int t, int best )
{
    int i, m = e[k].size();

    type temp;
    edge *ep;

    sign[k] = true;

    if( k == t )
        return best;

    for( i=0; i<m; i++ )
    {
        ep = &e[k][i];
        if( ep->f < ep->c && !sign[ ep->to ] )
        {
            if( ( temp = search( ep->to, t, min( best, ep->c - ep->f ) ) ) > 0 )
            {
                ep->f += temp;
                e[ ep->to ][ ep->rev_i ].f -= temp;
                return temp;
            }
        }
    }
    return 0;
}

ff::type ff::maxflow( int n, int s, int t )
{
    type total = 0, add = 0;

    do
    {
        total += add;
        memset( sign, 0, n );
    }
    while( ( add = search( s, t, max ) ) > 0 );

    return total;
}


ff maxf[20];
int n, b;
int fav[1000][20];
int limit[20];

void input( ) {
    int i, j;
    scanf( "%d%d", &n, &b );
    for( i=0; i<n; i++ ) {
        for( j=0; j<b; j++ )
            scanf( "%d", &fav[i][j] );
    }
    for( i=0; i<b; i++ )
        scanf( "%d", &limit[i] );
}

void create( ff &maxf ) {
    int i;
    maxf.init( );
    for( i=0; i<n; i++ )
        maxf.insert_edge( 0, i+1, 1 );
    for( i=0; i<b; i++ )
        maxf.insert_edge( n+i+1, n+b+1, limit[i] );
}

int main( ) {
    int res[20], i, j, k;

    input( );

    for( i=0; i<b; i++ ) {
        create( maxf[i] );
        res[i] = 0;
    }

    for( i=0; i<b-1; i++ ) {
        for( j=0; j<b-i; j++ ) {
            for( k=0; k<n; k++ )
                maxf[j].insert_edge( k+1, n+fav[k][j+i], 1 );
            res[j] += maxf[j].maxflow( n+b+2, 0, n+b+1 );
            if( res[j] == n )
                goto end;
        }
    }
end:
    printf( "%dn", i+1 );
    return 0;
}