BZOJ-2330: [SCOI2011]糖果（SPFA解差分约

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

差分约束。。。

代码（SPFA+SLF+LLL还是挺快滴，不过好像说建虚拟源的话就会华丽TLE，不知道为什么就是了。wiki上面不知道为什么会TLE：0，手测却无压力。。。）：

3c6d55fbb2fb43169ea50d0622a4462309f7d310.jpg.png

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
  
using namespace std ;
  
#define MAXN 100010
#define Clear( t ) memset( t , 0 , sizeof( t ) )
#define inf 0x7fffffff
  
struct edge {
    edge *next ;
    int t , d ;
} *head[ MAXN ] ;
  
void AddEdge( int s , int t , int d ) {
    edge *p = new( edge ) ; 
    p -> t = t , p -> d = d , p -> next = head[ s ] ;
    head[ s ] = p ;
}
  
int n , k , S ;
  
long long dist[ MAXN ] , num[ MAXN ] , sum = 0 ;
bool f[ MAXN ] ;
deque < int > Q ;
  
bool spfa(  ) {
    Clear( num ) ; 
    for ( int i = 0 ; i ++ < n ; ) dist[ i ] = inf , f[ i ] = false ;
    Q.clear(  ) ;
    for ( int i = 0 ; i ++ < n ; ) {
        sum ++ ; Q.push_back( i ) ; dist[ i ] = - 1 ; f[ i ] = true ;
    }
    while ( ! Q.empty(  ) ) {
        while ( ! Q.empty(  ) && dist[ Q.front(  ) ] > sum / Q.size(  ) + 1 ) Q.push_back( Q.front(  ) ) , Q.pop_front(  ) ;
        int v = Q.front(  ) ; Q.pop_front(  ) ; f[ v ] = false ; sum -= dist[ v ] ;
        if ( ( ++ num[ v ] ) > n ) return false ;
        for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( dist[ p -> t ] > dist[ v ] + p -> d ) {
            if ( f[ p -> t ] ) sum -= dist[ p -> t ] ;
            dist[ p -> t ] = dist[ v ] + p -> d ;
            sum += dist[ p -> t ] ;
            if ( ! f[ p -> t ] ) {
                f[ p -> t ] = true ;
                if ( Q.empty(  ) ) Q.push_back( p -> t ) ; else {
                    if ( dist[ p -> t ] < dist[ Q.front(  ) ] ) Q.push_front( p -> t ) ; else Q.push_back( p -> t ) ;
                }
            }
        }
    }
    return true ;
}
 
long long Min( long long x , long long y ) {
    if ( x > y ) return y ; return x ;
}
  
int main(  ) {
    scanf( "%d%d" , &n , &k ) ;
    S = n + 1 ; Clear( head ) ;
    while ( k -- ) {
        int x , a , b ; scanf( "%d%d%d" , &x , &a , &b ) ;
        switch ( x ) {
            case 1 :
                AddEdge( a , b , 0 ) , AddEdge( b , a , 0 ) ;
                break ;
            case 2 :
                AddEdge( a , b , - 1 ) ;
                break ;
            case 3 :
                AddEdge( b , a , 0 ) ;
                break ;
            case 4 :
                AddEdge( b , a , - 1 ) ;
                break ;
            case 5 :
                AddEdge( a , b , 0 ) ;
                break ; 
        }
    }
    if ( ! spfa(  ) ) printf( "-1\n" ) ; else {
        long long ans = 0 ;
        for ( int i = 0 ; i ++ < n ; )  ans -= dist[ i ] ;
        printf( "%lld\n" , ans ) ;
    }
    return 0 ;
}