上课了
竞赛班悲惨，信息竞赛班更悲惨。迟了若干天才放假不说，居然提前了这么多天上课……
省选集训，按照徐持衡老师的安排，早上做题目，下午讲课。第一天的情况是：上午一套3道题，4小时完成。严格要求，一人坐一排，断网，不准讨论，上厕所要申请。一个和数有关的题，一道网络流，一道可以说是DP也可以说是Ad Hoc的题。
下午，讲网络流。回顾BFS，介绍Dinic，重点讲SAP。掌握两种没必要……所以我坚持写Dinic。把以前过USACO的程序找出来一测，发现奇慢无比……好像又有地方写错了。于是重新写，调了大半天，改正若干错误，终于过了。我怎么觉得我的代码能力下降了，写出来能有这么多低级错误。需要磨合！razhangwei大牛的SAP比网上的HLPP还要快，Orz…
下午除了把早上的题目过了外，还写了下NOI06的profit，最大获利，经典的网络流，在开空间的时候犯了严重的错误，艰苦的调试后改正。
我来贴巨丑无比的代码，否则太对不起我在这里装的代码高亮的插件了。
#include <iostream> #include <fstream> using namespace std; FILE* fin = fopen( "profit.in" , "r" ); FILE* fout = fopen( "profit.out" , "w" ); const int INF = 100000000; const int MAX_V = 55002 , MAX_E = 155000; int hLink[ MAX_V + 1 ]; int S , T; int ans; struct Edge { int from , to , wei; int next , bro; } edge[ MAX_E * 2 + 1 ]; int eCnt; void _ins( int from , int to , int wei , int bro ) { ++ eCnt; edge[ eCnt ].from = from; edge[ eCnt ].to = to; edge[ eCnt ].wei = wei; edge[ eCnt ].bro = bro; edge[ eCnt ].next = hLink[ from ]; hLink[ from ] = eCnt; } void ins( int from , int to , int wei ) { _ins( from , to , wei , eCnt + 2 ); _ins( to , from , 0 , eCnt ); } int level[ MAX_V + 1 ]; int queue[ MAX_V + 1 ]; int qH , qT; bool BFS() { queue[ qH = 0 ] = S; qT = 1; memset( level , 0 , sizeof( level ) ); level[ S ] = 1; while ( qH != qT ) { for( int i = hLink[ queue[ qH ] ] ; i ; i = edge[ i ].next ) { if ( level[ edge[ i ].to ] || edge[ i ].wei == 0 ) continue; level[ edge[ i ].to ] = level[ queue[ qH ] ] + 1; queue[ qT ++ ] = edge[ i ].to; } ++ qH; } return level[ T ] != 0; } int stack[ MAX_V + 2 ] , top; int reach[ MAX_V + 2 ]; int last[ MAX_V + 2 ]; void DFS() { stack[ top = 1 ] = S; last[ 1 ] = hLink[ S ]; while ( top ) { if ( stack[ top ] != T ) { bool noUse = true; for( int i = last[ top ] ; i ; i = edge[ i ].next ) { if ( level[ edge[ i ].from ] + 1 != level[ edge[ i ].to ] ) continue; last[ top ] = edge[ i ].next; reach[ top ] = i; stack[ ++ top ] = edge[ i ].to; last[ top ] = hLink[ stack[ top ] ]; noUse = false; break; } if ( noUse ) { level[ stack[ top -- ] ] = 0; } } else { int minFlow = INF; for( int i = 1 ; i < top ; ++ i ) if ( minFlow > edge[ reach[ i ] ].wei ) minFlow = edge[ reach[ i ] ].wei; ans += minFlow; for( int i = 1 ; i < top ; ++ i ) { edge[ reach[ i ] ].wei -= minFlow; edge[ edge[ reach[ i ] ].bro ].wei += minFlow; } for( int i = 1 ; i < top ; ++ i ) { if ( edge[ reach[ i ] ].wei == 0 ) { top = i; break; } } } } } int n , m; int main() { fscanf( fin , "%d %d" , &n , &m ); S = 1; T = n + m + 2; for ( int i = 1 ; i <= n ; ++ i ) { int t; fscanf( fin , "%d" , &t ); ins( S , i + 1 , t ); } for ( int i = 1 ; i <= m ; ++ i ) { int a , b , c; fscanf( fin , "%d %d %d" , &a , &b , &c ); ins( a + 1 , i + n + 1 , INF ); ins( b + 1 , i + n + 1 , INF ); ins( i + n + 1 , T , c ); ans -= c; } while ( BFS() ) { DFS(); } fprintf( fout , "%dn" , - ans); fclose( fin ); fclose( fout ); } |
希望明天能做得好一点。
关于 BillWSY这是一个个人的Blog。我是一名普通的大学生，平时喜欢玩玩电脑，参加信息学奥赛。生活中总有那么一点东西，希望与大家一同分享。欢迎大家来到我的Blog。
