题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1565
2014刷的第一道题~~
裸的最小割模型，但是我们发现有些点相互依赖，这个在直接建图之后是无法割去的，那么求一次SCC，对于每个大小大于1的SCC的点，连到汇点，连一无穷大的边，表示强制割掉，然后跑最大流。
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std ;
#define MAXN 40
#define inf 0x7fffffff
#define MAXV 2010
struct edge{
edge *next ,*pair ;
int t , f ;
};
struct network{
edge *head[ MAXV ];
network( ){
memset( head ,0,sizeof( head ));
}
void Add(int s ,int t ,int f ){
edge *p =new( edge );
p -> t = t , p -> f = f , p -> next = head[ s ];
head[ s ]= p ;
}
void AddEdge(int s ,int t ,int f ){
Add( s , t , f ),Add( t , s ,0);
head[ s ]-> pair = head[ t ], head[ t ]-> pair = head[ s ];
}
int h[ MAXV ], gap[ MAXV ], S , T ;
edge *d[ MAXV ];
int sap(int v ,int flow ){
if( v == T )return flow ;
int rec =0;
for( edge *p = d[ v ]; p ; p = p -> next )if( p -> f && h[ v ]== h[ p -> t ]+1){
int ret =sap( p -> t ,min( flow - rec , p -> f ));
p -> f -= ret , p -> pair -> f += ret , d[ v ]= p ;
if(( rec += ret )== flow )return flow ;
}
if(!(-- gap[ h[ v ]])) h[ S ]= T ;
gap[++ h[ v ]]++, d[ v ]= head[ v ];
return rec ;
}
int maxflow( ){
int rec =0;
for(int i =0; i ++< T ;) h[ i ]= gap[ i ]=0, d[ i ]= head[ i ];
gap[ S ]= T ;
while( h[ S ]< T ) rec +=sap( S , inf );
return rec ;
}
} net ;
int node[ MAXN ][ MAXN ], V =0, n , m , sum =0, ws[ MAXV ];
stack <int> S ;
int dfn[ MAXV ], low[ MAXV ], scc[ MAXV ], size[ MAXV ], cnt =0;
bool f[ MAXV ];
void Tarjan(int v ){
dfn[ v ]= low[ v ]=++ cnt ;
S.push( v ), f[ v ]=true;
for( edge *p = net.head[ v ]; p ; p = p -> next )if( p -> f ){
if(! dfn[ p -> t ]){
Tarjan( p -> t );
low[ v ]=min( low[ v ], low[ p -> t ]);
}else if( f[ p -> t ]) low[ v ]=min( low[ v ], low[ p -> t ]);
}
if( low[ v ]== dfn[ v ]){
int u ;
do{
u = S.top( ); S.pop( );
f[ u ]=false, scc[ u ]= v , size[ v ]++;
}while( u != v );
}
}
int main( ){
scanf("%d%d",&n ,&m );
for(int i =0; i < n ; i ++)for(int j =0; j < m ; j ++) node[ i ][ j ]=++ V ;
net.S =++ V ; net.T =++ V ;
for(int i =0; i < n ; i ++)for(int j =0; j < m ; j ++){
int x , r , c ;scanf("%d",&x ); ws[ node[ i ][ j ]]= x ;
if( x >0) net.AddEdge( net.S , node[ i ][ j ], x ), sum += x
;else net.AddEdge( node[ i ][ j ], net.T ,- x );
scanf("%d",&x );
while( x --){
scanf("%d%d",&r ,&c );
net.AddEdge( node[ r ][ c ], node[ i ][ j ], inf );
}
}
for(int i =0; i < n ; i ++)for(int j =0; j < m -1; j ++){
net.AddEdge( node[ i ][ j ], node[ i ][ j +1], inf );
}
memset( dfn ,0,sizeof( dfn ));
memset( f ,false,sizeof( f ));
memset( size ,0,sizeof( size ));
for(int i =0; i ++< net.S -1;)if(! dfn[ i ]){
Tarjan( i );
}
for(int i =0; i ++< net.S -1;)if( size[ scc[ i ]]>1){
net.AddEdge( i , net.T , inf );
}
printf("%d\n", sum - net.maxflow( ));
return 0;
}
网友评论