# 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
{
memset( sign, 0, n );
}
while( ( add = search( s, t, max ) ) > 0 );

}

ff maxf;
int n, b;
int fav;
int limit;

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

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