BZOJ-1927: [Sdoi2010]星际竞速（费用流）

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

明显的费用流模型：首先，只看航线，这是一个拓扑图，那么我们就可以想到最小路径覆盖，将每个点i拆成vi,ui,连边(S,vi,1,0),(ui,T,1,0),然后对于每条航线(s,t,d),连边（v(min(s,t)),u(max(s,t)),1,d）,然后考虑到直接跳跃到某个点的问题，那么连(S,ui,1,ai),然后跑一次费用流，最小费用即为答案。

代码：

960a304e251f95ca12e054d5cb177f3e670952b8.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define MAXN 2010
#define inf 0x7fffffff
 
struct network {
     
    int S , T ;
     
    struct edge {
        edge *next , *pair ;
        int t , f , c ;
    } *head[ MAXN ] ;
     
    network(  ) {
        memset( head , 0 , sizeof( head ) ) ;
    }
     
    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 dist[ MAXN ] , slack[ MAXN ] , cost ;
    bool f[ MAXN ] ;
     
    int aug( int v , int flow ) {
        if ( v == T ) {
            cost += flow * dist[ S ] ; 
            return flow ;
        }
        f[ v ] = true ;
        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 ++ < T ; ) if ( ! f[ i ] ) delta = min( delta , slack[ i ] ) ;
        if ( delta == inf ) return false ;
        for ( int i = 0 ; i ++ < T ; ) if ( f[ i ] ) dist[ i ] += delta ;
        return true ;
    }
     
    int costflow(  ) {
        cost = 0 ;
        memset( dist , 0 , sizeof( dist ) ) ;
        do {
            for ( int i = 0 ; i ++ < T ; ) slack[ i ] = inf ;
            do {
                memset( f , false , sizeof( f ) ) ;
            } while ( aug( S , inf ) ) ;
        } while ( relabel(  ) ) ;
        return cost ;
    }
     
} net ;
 
int node[ MAXN ][ 2 ] , V = 0 , n , m ;
 
int main(  ) {
    scanf( "%d%d" , &n , &m ) ;
    for ( int i = 0 ; i ++ < n ; ) node[ i ][ 0 ] = ++ V , node[ i ][ 1 ] = ++ V ;
    net.S = ++ V ; net.T = ++ V ;
    for ( int i = 0 ; i ++ < n ; ) {
        int x ; scanf( "%d" , &x ) , net.AddEdge( net.S , node[ i ][ 1 ] , 1 , x ) ;
    }
    while ( m -- ) {
        int s , t , d ; scanf( "%d%d%d" , &s , &t , &d ) ;
        net.AddEdge( node[ min( s , t ) ][ 0 ] , node[ max( s , t ) ][ 1 ] , 1 , d ) ;
    }
    for ( int i = 0 ; i ++ < n ; ) net.AddEdge( net.S , node[ i ][ 0 ] , 1 , 0 ) , net.AddEdge( node[ i ][ 1 ] , net.T , 1 , 0 ) ;
    printf( "%d\n" , net.costflow(  ) ) ;
    return 0 ;
}