Poj Solution 1149

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

#include <list>
#include <vector>

using namespace std;



class pre_f
{

public:

    enum{ MAX = 1000000000 };        //���������
    enum{ size = 103 };                //ͼ�����ģ(*)

    // ����һ��� from �� to �� ��Ϊ c �ı�
    void insert_edge( int from, int to, int c );
    // ɾ�����б�
    void clear();
    //��ڵ���Ϊnodenum (0...nodenum-1 ) ������� begin ΪԴ, endΪ��                                
    int maxflow( int nodenum, int begin, int end );

private:
    /* needn't care */

    struct edge
    {
        int to;
        int f, c;
        int rev_i;
    };//�ߵĶ���

    int h[size];    //�߶�
    int r[size];    //����
    int cur[size];    //��ǰ���ǵı�ָ��

    vector<edge> e[size];    //�ڽӱ�
    list<int> l;        //����t��

    int n, s, t;        //������Դ�� ��

    void push( int a, edge &s );
    void lift( int a );
    void init();
    void dischange( int a );

};

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


void pre_f::insert_edge( int from, int to, int c )
{
    edge e1 = { to, 0, c, e[to].size() }, e2 = { from, 0, 0, e[from].size() };
    
    e[from].push_back( e1 );
    e[to].push_back( e2 );

}

void pre_f::clear()
{
    int i;
    for( i=0; i<size; i++ )
        e[i].clear();
    
    l.clear();
}

void pre_f::push( int a, edge &s )
{
    int y = s.c - s.f, x = r[a]<y?r[a]:y;
    s.f += x;
    e[ s.to ][ s.rev_i ].f = - s.f;
    r[a] -= x;
    r[s.to] += x;
}

void pre_f::lift( int a )
{
    int i, t = size*10;

    for( i=0; i<e[a].size(); i++ )
        if( e[a][i].f < e[a][i].c && t > h[ e[a][i].to ] )
            t = h[ e[a][i].to ];
    h[a] = t + 1;
}

void pre_f::init()
{
    int i;
    for( i=0; i<n; i++ )
        h[i] = 0, r[i] = 0;
    
    h[s] = n;
    r[s] = MAX;

    for( i=0; i<e[s].size(); i++ )
        push( s, e[s][i] );

    l.clear();

    for( i=0; i<n; i++ )
    {
        cur[i] = 0;
        if( i != s && i != t )
            l.push_back( i );
    }

}

void pre_f::dischange( int a )
{
    int k;

    while( r[a] )
    {
        k = cur[a];
        if( k == e[a].size() )
        {
            lift( a );
            cur[a] = 0;
        }
        else if( e[a][k].c > e[a][k].f && h[a] == h[ e[a][k].to ] + 1 )
            push( a, e[a][k] );
        else cur[a]++;
    }
}

int pre_f::maxflow( int nodenum, int begin, int end )
{
    int h_old;
    list<int>::iterator it;

    n = nodenum, s = begin, t = end;

    init();

    for( it=l.begin(); it != l.end(); it++ )
    {
        h_old = h[ *it ];
        dischange( *it );
        if( h_old < h[ *it ] )
        {
            l.push_front( *it );
            l.erase( it );
            it = l.begin();
        }
    }

    return MAX - r[s];
}


/***********************************************************/

#include <stdio.h>

int pig[1000];
int pre[1000];

#include <memory.h>
pre_f mf;
bool sign[102][102];

int main()
{
    int n, m, i, j, k, h;
    scanf( "%d %d", &m, &n );

    memset( sign, 0, sizeof(sign) );

    for( i=0; i<m; i++ )
    {
        scanf( "%d", &pig[i] );
        pre[i] = -1;
    }
    
    for( i=2; i<n+2; i++ )
    {
        scanf( "%d", &h );
        k = 0;
        while( h-- )
        {
            scanf( "%d", &j );
            j--;
            if( pre[j] < 0 )
            {
                k += pig[j];                
            }
            else if( !sign[pre[j]][i] )
            {
                mf.insert_edge( pre[j], i, 2000000 );
                sign[pre[j]][i] = true;
            }

            pre[j] = i;
        }

        if( k )
            mf.insert_edge( 0, i, k );

        scanf( "%d", &k );
        mf.insert_edge( i, 1, k );
    }

    printf( "%d", mf.maxflow( n+2, 0, 1 ) );

    return 0;

}