Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
救命呀,WA了 n 次了, 除了 原点 可以有2, 还有什么可注意的呀,代码见内55555555555555555555555555555!#include<iostream> #include<vector> using namespace std; class Stack { public: Stack() : top( -1 ) { } int pop() { return stack[ top -- ]; } void push( int data ) { stack[ ++ top ] = data; } bool isEmpty() { return top == -1; } int getSize() { return top; } private: int stack[ 55 ]; int top; }; const int max_int = 99999999; int graph[ 55 ][ 55 ] = { 0 }; int from[ 55 ][ 11 ], to[ 55 ][ 11 ]; int path[ 55 ]; int P, N; int maxFlow = 0; Stack stack[ 55 ]; int stackSize = 0; int times[ 55 ] = { 0 }, flow[ 55 ] = { 0 }; void createGraph(); bool findPath(); bool ford_fulkerson(); void solve(); int main() { createGraph(); solve(); return 0; } void createGraph() { int weight; scanf( "%d%d", &P, &N ); for ( int i = 1; i <= N; i ++ ) { scanf( "%d", &weight ); for ( int j = 0; j < P; j ++ ) scanf( "%d", &from[ i ][ j ] ); for ( int k = 0; k < P; k ++ ) scanf( "%d", &to[ i ][ k ] ); int u = 0; for ( int index = 1; index <= i - 1; index ++ ) { bool mark = true; for ( int index_ = 0; index_ < P; index_ ++ ) if ( from[ i ][ index_ ] != 2 && to[ index ][ index_ ] != from[ i ][ index_ ] ) mark = false; if ( mark ) { graph[ index ][ i ] = weight; } } int ind; for ( ind = 0; ind < P; ind ++ ) if ( from[ i ][ ind ] == 1 ) break; if ( ind == P ) { graph[ 0 ][ i ] = weight; } for ( ind = 0; ind < P; ind ++ ) if ( to[ i ][ ind ] != 1 ) break; if ( ind == P ) { graph[ i ][ N + 1 ] = max_int; } } } bool findPath() { int qFront, qRear; int queue[ 55 ]; bool mark[ 55 ]; int i; for ( i = 0; i <= N + 1; i ++ ) mark[ i ] = false; queue[ 0 ] = 0; mark[ 0 ] = true; qFront = 0; qRear = 1; for ( queue[ 0 ] = 0; qFront < qRear; qFront ++ ) { int cur = queue[ qFront ]; for ( i = 0; i <= N + 1; i ++ ) { if ( graph[ cur ][ i ] ) if ( ! mark [ i ] ) { mark[ i ] = true; path[ i ] = cur; if ( i == N + 1 ) return true; queue[ qRear ++ ] = i; } } } return false; } bool ford_fulkerson() { if ( !findPath( ) ) return false; int min = max_int; int i; for ( i = N + 1; i != 0; i = path[ i ] ) { if ( graph[ path [ i ] ][ i ] < min ) min = graph[ path[ i ] ][ i ]; } for ( i = N + 1; path[ i ] != 0; i = path[ i ] ) { stack[ stackSize ].push( path[ i ] ); } times[ stackSize ] = stack[ stackSize ].getSize(); flow[ stackSize ] = min; stackSize ++; for ( i = N + 1; i != 0; i = path[ i ] ) { graph[ path[ i ] ][ i ] -= min; graph[ i ][ path[ i ] ] += min; } maxFlow += min; return true; } void solve() { while ( ford_fulkerson( ) ); int total = 0; bool mark = true; for ( int k = 0; k < stackSize; k ++ ) { if ( times[ k ] == 0 ) mark = false; total += times[ k ]; } if ( ! mark ) total ++; printf( "%d %d\n", maxFlow, total ); for ( int i = 0; i < stackSize; i ++ ) { if ( times[ i ] != 0 ) { int temp = stack[ i ].pop(); while ( ! stack[ i ].isEmpty() ) { cout << temp << ' '; temp = stack[ i ].pop(); cout << temp << ' ' << flow[ i ] << endl; } } else { cout << stack[ i ].pop() << ' ' << flow[ i ] << endl; } } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator