首页 > 代码库 > spfa + slf优化

spfa + slf优化

2024-08-15 23:11:48   248人阅读

最近在练习费用流 ， 不是要用spfa吗 ，我们教练说：ns学生写朴素的spfa说出去都让人笑 。

QwQ，所以就去学了一下优化 。

slf优化就是双向队列优化一下，本来想用lll优化，可是优化后我tm居然t了（那道题特地卡spfa），所以lll优化太迷了 ，还是只用slf优化好 。

 1 #include <iostream> 2 #include <cstdlib> 3 #include <cstring> 4 #include <cstdio> 5 #include <deque> 6 const int inf = 1 << 30 , maxn = 100000 + 11 , M = 200000 + 11  ;  7 using namespace std ;//1061109567 8 int n , m , head[maxn]  , dis[maxn] , cnt , sum , tot ; 9 bool mark[maxn] ; 10 struct id11 {12     int nxt ,to , val ;13 } edge[M] ;14 deque < int > Q ;15 16 17 inline void Init ( )18 {19     freopen( "NSOOJ#10719.in" , "r" , stdin  ) ;20     freopen( "NSOOJ#10719.out" , "w" , stdout ) ;21 }22 23 int read( )24 {25     char ch = getchar( ) ; int k = 1 , ret = 0 ;26     while( ch < ‘0‘ || ch > ‘9‘ ) { if( ch == ‘-‘ ) k = -1 ; ch = getchar( ) ; }27     while( ch >= ‘0‘ && ch <= ‘9‘ ) ret = ret * 10 + ch - ‘0‘ , ch = getchar( ) ;28     return k * ret ;29 }30 31 void add( int u , int v , int va )32 {33     edge[++cnt].nxt = head[u] , edge[cnt].to = v ;34     edge[cnt].val = va , head[u] = cnt ;35 }36 37 void input(  )38 {39     n = read()  , m = read( ) ;40     int u ,v , c ;41     memset( head , -1 , sizeof(head)) ;42     for( int x = 1 ; x <= m ; ++x )43     {44         u = read( ) , v = read( ) , c = read( ) ;45         add( u ,v , c )  ;46     }47 }48 49 void spfa( )50 {51     memset( dis , 127/2 , sizeof(dis) ) ;52     dis[1] = 0 , mark[1] = true ;53     Q.push_back( 1 ) ;54     while( !Q.empty( ) )55     {56         int u = Q.front( ) ; Q.pop_front( ) ; mark[u] = false ;57     58         for( int i = head[u] ; ~i ; i = edge[i].nxt )59         {60             int v = edge[i].to ; 61             if( dis[v] > dis[u] + edge[i].val )62             {63                 dis[v] = dis[u] + edge[i].val ;64                 if( !mark[v] )65                 {66                     mark[v] = true ; 67                     if( Q.empty( ) || dis[v] > dis[Q.front( )]  ) Q.push_back( v ) ;68                     else Q.push_front( v ) ;69                     70                 }71             72             }73         }74     }75     if( dis[n] == 1061109567 ) printf( "%d\n" , -1 ) ;76     else printf( "%d\n" , dis[n] ) ;77 }78 79 80 int main( )81 {82 //    Init( ) ; 83     input( ) ;84     spfa( ) ;85 //    fclose( stdin ) ;86 //       fclose( stdout ) ;87     return 0 ;88 }

 

spfa + slf优化


联系
我们