Pku1149 PIGS卖锗
Time Limit:2000MS Memory Limit:165536K
Total Submit:39 Accepted:22
Case Time Limit:1000MS
Description
Emmy在一个养猪场工作。这个养猪场有M个锁着的猪圈，但Emmy并没有钥匙。顾客会到养猪场来买猪，一个接着一个。每一位顾客都会有一些猪圈的钥匙，他们会将这些猪圈打开并买走固定数目的猪。所有顾客有的钥匙和他们需要买猪的数量在事先都告诉了Emmy，于是Emmy要订一个计划，使得卖出去的猪最多。买卖的过程是这样的：一个顾客前来，并打开所有他可以打开的猪圈。然后Emmy从这些猪圈里牵出固定数目的猪卖给顾客（最多只能和顾客需要数相等），并可以重新安排这些开着的猪圈中的猪。
每个猪圈可以存放任意数目的猪。
写一个程序，使得Emmy能够卖出去尽可能多的猪。
Input
{dy}行有两个整数：M和N，表示猪圈数和顾客数。
第二行有M个整数，表示每个猪圈初始时有多少猪。
接下来的N行按照前来的次序描述了每一个顾客，每行的格式如下：
A K1 K2…KA B
A表示该顾客拥有的钥匙数，K1...KA表示每个钥匙所对应的猪圈，B表示该顾客需要购买的猪的数目。
Output
仅包含一个整数，即最多能卖出去的猪的数目。
Sample Input
Sample Output
7
Hint
数据规模
1 ≤ M ≤ 1000
1 ≤ N ≤ 100
极度郁闷的C++的网络流。。搞了1天发现题目看错了。。买猪的不是把猪圈打开，是交换猪圈中的猪。。连边的话 前面的人可以交换自己打开的猪圈 那么 后面的人可以从前面的人打开的猪圈中拿随意的猪。。所以后面的人连上前面的人一条边就行了。。。
//Writer tclsm
#include <iostream>
using namespace std;
const
int maxn = 1107, maxm = 1000007 , maxnum = 100000000 , empty = -1;
int n , m , tot , a[ maxn ] , now[ maxn ] , dep[ maxn ] , zz[ maxn ] , list[ maxn ];
int y[ maxm ] , opp[ maxm ] , flow[ maxm ] , pre[ maxm ];
int first , last ;
void cnt ( int fir , int lst , int val , int op )
{
tot++;
pre[ tot ] = now[ fir ];
now[ fir ] = tot;
y [ tot ] = lst;
opp[ tot ] = op;
flow[ tot ] = val;
}
void cnet( int fir , int lst , int val )
{
cnt( fir , lst , val , tot+2 );
cnt( lst , fir , 0 , tot );
}
void init()
{
int i , j , num , fir , lst;
scanf( "%d %d" , &m , &n );
first = n+m+1; last = first+1;
tot = 0;
for ( int i = 1 ; i <= m ; i++ ) list[ i ] = i+n;
for ( int i = 1 ; i <= m ; i++ )
{
scanf( "%d" , &num );
cnet( i+n , last , num );
}
for ( i = 1 ; i <= n ; i++ )
{
fir = i;
for ( scanf( "%d" , &j ) ; j >= 1 ; j-- )
{
scanf( "%d" , &lst );
cnet( fir , list[ lst ] , maxnum );
list[ lst ] = fir;
}
scanf( "%d" , &num );
cnet( first , fir , num );
}
}
int add( int x , int cost )
{
int res , minn , mark , xx;
if ( x == last ) return( cost );
res = 0;
mark = now[ x ];
while ( mark > 0 )
{
minn = 0;
xx = y[ mark ];
if ( ( dep[ x ]+1 == dep[ xx ] ) & ( flow[ mark ] > 0 ) )
minn = add( xx , min( cost , flow[ mark ] ) );
flow[ mark ] -= minn;
flow[ opp[ mark ] ] += minn;
res += minn;
cost -= minn;
if ( cost <= 0 ) break;
mark = pre[ mark ];
}
dep[ x ] = empty;
return( res );
}
bool bfs()
{
int head , tail;
int x , xx , mark;
memset( dep , empty , sizeof( dep ) );
head = 1; tail = 1;
zz[ 1 ] = first;
dep[ first ] = 1;
do
{
x = zz[ head ];
mark = now[ x ];
while ( mark > 0 )
{
xx = y[ mark ];
if ( ( flow[ mark ] > 0 ) & ( dep[ xx ] == empty ) )
{
tail++;
zz[ tail ] = xx ;
dep[ xx ] = dep[ x ]+1;
}
mark = pre[ mark ];
}
head++;
}
while ( head <= tail );
if ( dep[ last ] > 0 ) return( true );
return( false );
}
void print()
{
int res;
res = 0;
while ( bfs() ) res += add( first , maxnum );
printf( "%d\n" , res );
}
int main()
{
init();
print();
}
3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6
