注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-1266: [AHOI2006]上学路线route(最短路+最小割)  

2014-02-03 22:04:00|  分类: oi,bzoj,网络流,s |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


按题意跑一次SPFA之后再建最短路图,然后跑一次最小流求最小割即可。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <deque>

  •  

  • using namespace std ;

  •  

  • #define MAXV 1010

  • #define pb push_back

  • #define pf push_front

  • #define MAXM 150010

  • #define inf 0x7fffffff

  • #define MAXN 1010

  •  

  • struct network {

  •          

  •     struct edge {

  •         edge *next , *pair ;

  •         int t , f ;

  •     } *head[ MAXV ] ;

  •          

  •     void Add( int s , int t , int f ) {

  •         edge *p = new( edge ) ;

  •         p -> t = t , p -> f = f , p -> next = head[ s ] ;

  •         head[ s ] = p ;

  •     }

  •          

  •     void AddEdge( int s , int t , int f ) {

  •         Add( s , t , f ) , Add( t , s , 0 ) ;

  •         head[ s ] -> pair = head[ t ] , head[ t ] -> pair = head[ s ] ;

  •     }

  •          

  •     int S , T ;

  •          

  •     network(  ) {

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

  •     }

  •          

  •     int h[ MAXV ] , gap[ MAXV ] ;

  •     edge *d[ MAXV ] ;

  •          

  •     int sap( int v , int flow ) {

  •         if ( v == T ) return flow ;

  •         int rec = 0 ;

  •         for ( edge *p = d[ v ] ; p ; p = p -> next ) if ( p -> f && h[ v ] == h[ p -> t ] + 1 ) {

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

  •             p -> f -= ret , p -> pair -> f += ret , d[ v ] = p ;

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

  •         }

  •         if ( ! ( -- gap[ h[ v ] ] ) ) h[ S ] = T ;

  •         gap[ ++ h[ v ] ] ++ , d[ v ] = head[ v ] ;

  •         return rec ;

  •     }

  •          

  •     int maxflow(  ) {

  •         int flow = 0 ;

  •         memset( h , 0 , sizeof( h ) ) ;

  •         memset( gap , 0 , sizeof( gap ) ) ;

  •         for ( int i = 0 ; i ++ < T ; ) d[ i ] = head[ i ] ;

  •         gap[ S ] = T ;

  •         while ( h[ S ] < T ) flow += sap( S , inf ) ;

  •         return flow ;

  •     }

  •          

  • } net ;

  •  

  • struct graph {

  •      

  •     struct edge {

  •         edge *next ;

  •         int t , d , c ;

  •     } *head[ MAXN ] ;

  •      

  •     int n ;

  •      

  •     graph(  ) {

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

  •     }

  •      

  •     void Add( int s , int t , int d ) {

  •         edge *p = new( edge ) ;

  •         p -> t = t , p -> d = d , p -> next = head[ s ] ;

  •         head[ s ] = p ;

  •     }

  •      

  •     void AddEdge( int s , int t , int d ) {

  •         Add( s , t , d ) , Add( t , s , d ) ;

  •     }

  •      

  •     deque < int > q ;

  •     int dist[ MAXN ] ;

  •     bool f[ MAXN ] ;

  •      

  •     void spfa( int S ) {

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

  •         q.clear(  ) ;

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

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

  •         while ( ! q.empty(  ) ) {

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

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

  •                 if ( dist[ p -> t ] > dist[ v ] + p -> d ) {

  •                     dist[ p -> t ] = dist[ v ] + p -> d ;

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

  •                         f[ p -> t ] = true ;

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

  •                             q.pf( p -> t ) ;

  •                         } else q.pb( p -> t ) ;

  •                     }

  •                 }

  •             }

  •         }

  •     }

  •      

  • } g ;

  •  

  • int e[ MAXM ][ 4 ] , n , m ;

  •  

  • int main(  ) {

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

  •     g.n = n ;

  •     for ( int i = 0 ; i ++ < m ; ) {

  •         scanf( "%d%d%d%d" , &e[ i ][ 0 ] , &e[ i ][ 1 ] , &e[ i ][ 2 ] , &e[ i ][ 3 ] ) ;

  •         g.AddEdge( e[ i ][ 0 ] , e[ i ][ 1 ] , e[ i ][ 2 ] ) ;

  •     }

  •     g.spfa( 1 ) ;

  •     printf( "%d\n" , g.dist[ n ] ) ;

  •     net.S = 1 , net.T = n ;

  •     for ( int i = 0 ; i ++ < m ; ) {

  •         if ( g.dist[ e[ i ][ 1 ] ] == g.dist[ e[ i ][ 0 ] ] + e[ i ][ 2 ] ) {

  •             net.AddEdge( e[ i ][ 0 ] , e[ i ][ 1 ] , e[ i ][ 3 ] ) ;

  •         }

  •         if ( g.dist[ e[ i ][ 0 ] ] == g.dist[ e[ i ][ 1 ] ] + e[ i ][ 2 ] ) {

  •             net.AddEdge( e[ i ][ 1 ] , e[ i ][ 0 ] , e[ i ][ 3 ] ) ;

  •         }

  •     }

  •     printf( "%d\n" , net.maxflow(  ) ) ;

  •     return 0 ;

  • }



  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018