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

}

```
This entry was posted in poj. Bookmark the permalink.