BZOJ-1565: [NOI2009]植物大战僵尸（Tarja

题目：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;

}