BZOJ-3442: 学习小组（费用流）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3442

写了一个跟标解不一样的建图方法，标解的方法我反而死活写不过囧死了。。。：

首先，对于每个人代表的点设为vi，每个小组的点设为ui，从S往vi连容量为k，费用0的边，从每个ui往T连n条边，第k条边的容量均为1，费用为ci*(k^2-(k-1)2)，对于每组匹配的vi，uj，从vi连uj容量1，费用-fj的边,然后，如果k>1,对于每个vi，连边到T，容量为k-1，费用为0，然后跑一次费用流答案就出来了。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <deque>

  

using namespace std ;

  

#define inf 0x7fffffff

#define MAXN 210

#define pf push_front

#define pb push_back

  

struct edge {

    edge *next , *pair ;

    int t , f , c ;

} *head[ MAXN ] ;

  

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 n , m , k , c[ MAXN ] , F[ MAXN ] , S , T , V , cost = 0 ;

char w[ MAXN ][ MAXN ] ;

  

int dist[ MAXN ] , slack[ MAXN ] ;

bool f[ MAXN ] ;

  

int aug( int v , int flow ) {

    if ( v == T ) {

        cost += flow * ( dist[ S ] - dist[ T ] ) ;

        return flow ;

    }

    f[ v ] = false ;

    int rec = 0 ;

    for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( p -> f && dist[ v ] == dist[ p -> t ] + p -> c && f[ p -> t ] ) {

        int ret = aug( p -> t , min( flow - rec , p -> f ) ) ;

        p -> f -= ret , p -> pair -> f += ret ;

        if ( ( rec += ret ) == flow ) return flow ;

    } else if ( p -> f ) slack[ p -> t ] = min( slack[ p -> t ] , dist[ p -> t ] - dist[ v ] + p -> c ) ;

    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 ;

}

 

deque < int > q ;

 

void Spfa(  ) {

    memset( f , false , sizeof( f ) ) ;

    for ( int i = 0 ; i ++ < V ; ) dist[ i ] = inf ;

    q.clear(  ) ;

    q.pf( T ) , dist[ T ] = 0 , f[ T ] = true ;

    while ( ! q.empty(  ) ) {

        int v = q.front(  ) ;

        q.pop_front(  ) , f[ v ] = false ;

        for ( edge *p = head[ v ] ; p ; p = p -> next ) {

            if ( ! p -> f && dist[ p -> t ] > dist[ v ] - p -> c ) {

                dist[ p -> t ] = dist[ v ] - p -> c ;

                if ( ! f[ p -> t ] ) {

                    f[ p -> t ] = true ;

                    if ( ! q.empty(  ) && dist[ p -> t ] < dist[ q.front(  ) ] ) {

                        q.pf( p -> t ) ;

                    } q.pb( p -> t ) ;

                }

            }

        }

    }

}

  

int costflow(  ) {

    Spfa(  ) ;

    do {

        do {

            for ( int i = 0 ; i ++ < V ; ) slack[ i ] = inf ;

            memset( f , true , sizeof( f ) ) ;

        } while ( aug( S , inf ) ) ;

    } while ( relabel(  ) ) ;

    return cost ;

}

  

int main(  ) {

    scanf( "%d%d%d" , &n , &m , &k ) ;

    S = n + m + 1 , T = V = n + m + 2 ;

    memset( head , 0 , sizeof( head ) ) ;

    for ( int i = 0 ; i ++ < m ; ) scanf( "%d" , c + i ) ;

    for ( int i = 0 ; i ++ < m ; ) scanf( "%d" , F + i ) ;

    for ( int i = 0 ; i ++ < n ; ) scanf( "%s" , w[ i ] + 1 ) ;

    for ( int i = 0 ; i ++ < n ; ) AddEdge( S , i , k , 0 ) ;

    for ( int i = 0 ; i ++ < n ; ) {

        if ( k - 1 ) AddEdge( i , T , k - 1 , 0 ) ;

        for ( int j = 0 ; j ++ < m ; ) if ( w[ i ][ j ] == '1' ) AddEdge( i , n + j , 1 , - F[ j ] ) ;

    }

    for ( int i = 0 ; i ++ < m ; ) for ( int j = 0 ; j ++ < n ; ) AddEdge( n + i , T , 1 , c[ i ] * ( j * j - ( j - 1 ) * ( j - 1 ) ) ) ;

    printf( "%d\n" , costflow(  ) ) ;

    return 0 ;

}