BZOJ-2245: [SDOI2011]工作安排（费用流）

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

明显是费用流吧？那么直接写就可以了。

代码（刚开始写zkw费用流T了半天，改成SPFA就A了额。。。话说网上找到的快的zkw代码都是加了当前弧的，不是说那啥其实是错的么。。。）：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>
 
using namespace std ;
 
#define pb push_back
#define pf push_front
 
#define maxn 260
#define maxm 260
#define maxv 1010
 
typedef long long ll ; 
 
const int inf = 0x7fffffff ;
 
struct edge {
    edge *next , *pair ;
    int t , f , c ; 
} *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 ; 
 
int dist[ maxv ] , pre[ maxv ] , minf[ maxv ] ;
bool f[ maxv ] ;
ll cost = 0 ; 
edge *aug[ maxv ] ;
 
deque < int > q ;
 
bool spfa(  ) {
    int temp ;
    for ( int i = 0 ; i ++ < V ; ) {
        dist[ i ] = inf , f[ i ] = false ;
    }
    q.clear(  ) ;
    q.pb( S ) , dist[ S ] = 0 , f[ S ] = true , pre[ S ] = 0 , minf[ S ] = inf ;
    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 ) {
            if ( ( temp = dist[ v ] + p -> c ) < dist[ p -> t ] ) {
                dist[ p -> t ] = temp , aug[ p -> t ] = p ; 
                pre[ p -> t ] = v , minf[ p -> t ] = min( minf[ v ] , p -> f ) ;
                if ( ! f[ p -> t ] ) {
                    if ( ! q.empty(  ) && dist[ q.front(  ) ] > dist[ p -> t ] ) {
                        q.pf( p -> t ) ; 
                    } else q.pb( p -> t ) ;
                    f[ p -> t ] = true ;
                }
            }
        }
    }
    if ( dist[ T ] == inf ) return false ;
    cost += ll( dist[ T ] ) * ll( minf[ T ] ) ;
    for ( int t = T ; pre[ t ] ; t = pre[ t ] ) {
        aug[ t ] -> f -= minf[ T ] , aug[ t ] -> pair -> f += minf[ T ] ;
    }
    return true ;
}
 
ll costflow(  ) {
    while ( spfa(  ) ) ;
    return cost ;
}
 
int n , m , t[ maxn ] , w[ maxn ] ;
 
int main(  ) {
    scanf( "%d%d" , &m , &n ) ;
    S = n + m + 1 , T = V = n + m + 2 ; 
    for ( int i = 0 ; i ++ < n ; ) {
        int x ; scanf( "%d" , &x ) ;
        AddEdge( S , i , x , 0 ) ;
    }
    for ( int i = 0 ; i ++ < m ; ) for ( int j = 0 ; j ++ < n ; ) {
        int val ; scanf( "%d" , &val ) ;
        if ( val ) AddEdge( j , n + i , inf , 0 ) ;
    }
    t[ 0 ] = 0 ;
    for ( int i = 0 ; i ++ < m ; ) {
        int cnt ; scanf( "%d" , &cnt ) ;
        for ( int j = 0 ; j ++ < cnt ; ) scanf( "%d" , t + j ) ;
        t[ cnt + 1 ] = inf ;
        for ( int j = 0 ; j ++ < cnt + 1 ; ) scanf( "%d" , w + j ) ;
        for ( int j = 0 ; j ++ < cnt + 1 ; ) {
            AddEdge( n + i , T , t[ j ] - t[ j - 1 ] , w[ j ] ) ;
        }
    }
    printf( "%lld\n" , costflow(  ) ) ;
    return 0 ; 
}