题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2879
经典的费用流模型，把每个厨师拆成sum(pi)个点就可以了，然后注意动态加点（增广路跑到一个可以拓展的点就拓展）
代码（BZOJ上可以改，但是目测还是没法分别过全部数据，第二点跑了3s+，第三个点1s+，目测被卡zkw费用流了）：
b3119313b07eca8005550992932397dda1448376.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define MAXN 50
#define MAXM 110
#define MAXP 810
#define MAXV 100010
#define clear( x )memset( x ,0,sizeof( x ))
#define inf 0x7fffffff
struct edge{
edge *next ,*pair ;
int t , f , c ;
edge ( ){
next = pair = NULL ;
}
}*head[ MAXV ];
void Add(int s ,int t ,int f ,int c ){
edge *p =new( edge );
p -> t = t , p -> f = f , p -> c = c , p -> next = head[ s ];
head[ s ]= p ;
}
void AddEdge(int s ,int t ,int f ,int c ){
Add( s , t , f , c ),Add( t , s ,0,- c );
head[ s ]-> pair = head[ t ], head[ t ]-> pair = head[ s ];
}
int S , T , V , node[ MAXM ][ MAXP ], w[ MAXV ][2];
bool visit[ MAXM ][ MAXP ];
int Time[ MAXN ][ MAXM ], n , m , p[ MAXN ], P =0;
int cost =0, dist[ MAXV ], slack[ MAXV ];
bool f[ MAXV ];
int aug(int v ,int flow ){
if( v == T ){
cost += dist[ S ]* flow ;return flow ;
}
if( w[ v ][1]< P )if(! visit[ w[ v ][0]][ w[ v ][1]+1]){
visit[ w[ v ][0]][ w[ v ][1]+1]=true;
node[ w[ v ][0]][ w[ v ][1]+1]=++ V ;
w[ V ][0]= w[ v ][0], w[ V ][1]= w[ v ][1]+1;
AddEdge( V , T ,1,0);
for(int i =0; i ++< n ;)AddEdge( i , V ,1, Time[ i ][ w[ V ][0]]* w[ V ][1]);
dist[ V ]=0; f[ V ]=true; slack[ V ]= inf ;
}
f[ v ]=false;int rec =0;
for( edge *p = head[ v ]; p ; p = p -> next )if( p -> f && f[ p -> t ]){
if( dist[ v ]== dist[ p -> t ]+ p -> c ){
int ret =aug( p -> t ,min( flow - rec , p -> f ));
p -> f -= ret , p -> pair -> f += ret ;
if(( rec += ret )== flow )return flow ;
}else slack[ p -> t ]=min( slack[ p -> t ], dist[ p -> t ]+ p -> c - dist[ v ]);
}
return rec ;
}
bool relabel( ){
int delta = inf ;
for(int i =0; i ++< V ;)if( f[ i ]) delta =min( delta , slack[ i ]);
if( delta == inf )return false;
for(int i =0; i ++< V ;)if(! f[ i ]) dist[ i ]+= delta ;
return true;
}
void costflow( ){
for(int i =0; i ++< V ;) dist[ i ]=0;
do{
for(int i =0; i ++< V ;) slack[ i ]= inf ;
do{
for(int i =0; i ++< V ;) f[ i ]=true;
}while(aug( S ,inf ));
}while(relabel( ));
}
int main( ){
scanf("%d%d",&n ,&m );
for(int i =0; i ++< n ;){
scanf("%d",&p[ i ]); P += p[ i ];
}
clear( head );
V = n ; S =++ V , T =++ V ;
for(int i =0; i ++< n ;){
AddEdge( S , i , p[ i ],0);
}
clear( visit ),clear( w );
visit[0][1]=true;
for(int i =0; i ++< n ;)for(int j =0; j ++< m ;)scanf("%d",&Time[ i ][ j ]);
for(int i =0; i ++< m ;){
visit[ i ][1]=true; node[ i ][1]=++ V ;
w[ V ][0]= i , w[ V ][1]=1;
AddEdge( V , T ,1,0);
for(int j =0; j ++< n ;)AddEdge( j , V ,1, Time[ j ][ i ]);
}
costflow( );
printf("%d\n", cost );
return 0;
}
终于把每个点都过了。。。第二个点卡zkw费用流，倒数几个点卡SPFA。。。实在火大就写了个分类，边数多就zkw，边数少就spfa+lll，终于过了。。。rank11。。还可以吧：
a2cc7cd98d1001e998c4f97aba0e7bec55e797cf.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define MAXN 50
#define MAXM 110
#define MAXP 810
#define MAXV 100010
#define clear( x ) memset( x , 0 , sizeof( x ) )
#define inf 0x7fffffff
void getint( int &t ) {
int ch ;
for ( ch = getchar( ) ; ! ( ch >= '0' && ch <= '9' ) ; ch = getchar( ) ) ;
t = ch - '0' ;
for ( ch = getchar( ) ; ch >= '0' && ch <= '9' ; ch = getchar( ) ) t *= 10 , t += ch - '0' ;
}
void putint( int t ) {
if ( ! t ) putchar( '0' )
; else {
int ans[ 20 ] ;
ans[ 0 ] = 0 ;
for ( ; t ; t /= 10 ) ans[ ++ ans[ 0 ] ] = t % 10 ;
for ( int i = ans[ 0 ] ; i ; i -- ) putchar( '0' + ans[ i ] ) ;
}
putchar( '\n' );
}
struct edge {
edge *next , *pair ;
int t , f , c ;
edge ( ) {
next = pair = NULL ;
}
} *head[ MAXV ] ;
void Add( int s , int t , int f ,int c ) {
edge *p = new( edge ) ;
p -> t = t , p -> f = f , p -> c = c , p -> next = head[ s ] ;
head[ s ] = p ;
}
void AddEdge( int s , int t , int f , int c ) {
Add( s , t , f , c ) , Add( t , s , 0 , - c ) ;
head[ s ] -> pair = head[ t ] , head[ t ] -> pair = head[ s ] ;
}
int S , T , V , node[ MAXM ][ MAXP ] , w[ MAXV ][ 2 ] , last[ MAXM ] ;
bool visit[ MAXM ][ MAXP ] ;
int Time[ MAXN ][ MAXM ] , n , m , p[ MAXN ] , P = 0 ;
int cost = 0 , dist[ MAXV ] , slack[ MAXV ] ;
bool f[ MAXV ] ;
int aug( int v , int flow ) {
if ( v == T ) {
cost += dist[ S ] * flow ; return flow ;
}
if ( w[ v ][ 1 ] < P ) if ( ! visit[ w[ v ][ 0 ] ][ w[ v ][ 1 ] + 1 ] ) {
visit[ w[ v ][ 0 ] ][ w[ v ][ 1 ] + 1 ] = true ;
node[ w[ v ][ 0 ] ][ w[ v ][ 1 ] + 1 ] = ++ V ;
w[ V ][ 0 ] = w[ v ][ 0 ] , w[ V ][ 1 ] = w[ v ][ 1 ] + 1 ;
AddEdge( V , T , 1 , 0 ) ;
for ( int i = 0 ; i ++ < n ; ) AddEdge( i , V , 1 , Time[ i ][ w[ V ][ 0 ] ] * w[ V ][ 1 ] ) ;
dist[ V ] = 0 ; f[ V ] = true ; slack[ V ] = inf ;
}
f[ v ] = false ; int rec = 0 ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( p -> f && f[ p -> t ] ) {
if ( dist[ v ] == dist[ p -> t ] + p -> c ) {
int ret = aug( p -> t , min( flow - rec , p -> f ) ) ;
p -> f -= ret , p -> pair -> f += ret ;
if ( ( rec += ret ) == flow ) return flow ;
} else slack[ p -> t ] = min( slack[ p -> t ] , dist[ p -> t ] + p -> c - dist[ v ] ) ;
}
return rec ;
}
bool relabel( ) {
int delta = inf ;
for ( int i = 0 ; i ++ < V ; ) if ( f[ i ] ) delta = min( delta , slack[ i ] ) ;
if ( delta == inf ) return false ;
for ( int i = 0 ; i ++ < V ; ) if ( ! f[ i ] ) dist[ i ] += delta ;
return true ;
}
void costflow( ) {
for ( int i = 0 ; i ++ < V ; ) dist[ i ] = 0 ;
do {
for ( int i = 0 ; i ++ < V ; ) slack[ i ] = inf ;
do {
for ( int i = 0 ; i ++ < V ; ) f[ i ] = true ;
} while ( aug( S ,inf ) ) ;
} while ( relabel( ) ) ;
}
int pre[ MAXV ] , Q[ MAXV * 10 ] , size = 0 ;
edge *Aug[ MAXV ] ;
void spfa( ) {
for ( int i = 0 ; i ++ < V ; ) dist[ i ] = inf , f[ i ] = false ;
int Head = 0 , tail = 0 , _d = 0 ; size = 1 ;
dist[ S ] = 0 , Q[ ++ tail ] = S , pre[ S ] = 0 , f[ S ] = true ;
while ( Head < tail ) {
while ( dist[ Q[ ++ Head ] ] > _d / size ) Q[ ++ tail ] = Q[ Head ] ;
int v = Q[ Head ] ; size -- ; _d -= dist[ v ] ;
f[ v ] = false ;
for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( p -> f && dist[ p -> t ] > dist[ v ] + p -> c ) {
if ( f[ p -> t ] ) _d -= dist[ p -> t ] ;
dist[ p -> t ] = dist[ v ] + p -> c ;
if ( ! f[ p -> t ] ) {
f[ p -> t ] = true ; Q[ ++ tail ] = p -> t ;
size ++ ;
}
_d += dist[ p -> t ] ;
pre[ p -> t ] = v , Aug[ p -> t ] = p ;
}
}
}
int main( ) {
getint( n ) , getint( m ) ;
for ( int i = 0 ; i ++ < n ; ) {
getint( p[ i ] ) ; P += p[ i ] ;
}
clear( head ) ;
V = n ; S = ++ V , T = ++ V ;
for ( int i = 0 ; i ++ < n ; ) {
AddEdge( S , i , p[ i ] , 0 ) ;
}
clear( visit ) , clear( w ) ;
visit[ 0 ][ 1 ] = true ;
for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < m ; ) getint( Time[ i ][ j ] ) ;
for ( int i = 0 ; i ++ < m ; ) {
visit[ i ][ 1 ] = true ; node[ i ][ 1 ] = ++ V ; last[ i ] = 1 ;
w[ V ][ 0 ] = i , w[ V ][ 1 ] = 1 ;
for ( int j = 0 ; j ++ < n ; ) AddEdge( j , V , 1 , Time[ j ][ i ] ) ;
AddEdge( V , T , 1 , 0 ) ;
}
if ( ( m + P ) * n > 20000 ) costflow( ) ; else {
for ( int i = 0 ; i ++ < P ; ) {
spfa( ) ; cost += dist[ T ] ; if ( i == P ) break ;
for ( int i = T ; pre[ i ] ; i = pre[ i ] ) Aug[ i ] -> f -- , Aug[ i ] -> pair -> f ++ ;
for ( int j = 0 ; j ++ < m ; ) if ( ! head[ node[ j ][ last[ j ] ] ] -> f ) {
node[ j ][ ++ last[ j ] ] = ++ V ;
for ( int k = 0 ; k ++ < n ; ) AddEdge( k , V , 1 , Time[ k ][ j ] * last[ j ] ) ;
AddEdge( V , T , 1 , 0 ) ;
}
}
}
putint( cost ) ;
return 0 ;
}
网友评论