Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

救命呀,WA了 n 次了, 除了 原点 可以有2, 还有什么可注意的呀,代码见内55555555555555555555555555555!

Posted by fantasyorg at 2008-04-07 13:12:33 on Problem 3436
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator