OJ Board

Code: Select all

#define SOURCE 36
#define SINK 37
#define FIRSTCMP 26

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

#include <queue>
using std::queue;

#include <string>
using std::string;

using std::min;

int f [ 38 ][ 38 ]; // 0..25 are chars, 26..35 are computers, 36 is source, 37 is sink, 
int p [ 38 ];
int totalWorks;

void process();
int bfs();

int main()
{
	char tempL [ 15 ];

	// initialize
	for ( int i = 0; i < 38; i++ )
	{
		for ( int j = 0; j < 38; j++ )
		{
		   f[ i ][ j ] = 0;
		}
	}

	totalWorks = 0;


	while ( cin.getline( tempL, 15, '\n' ) )
	{
		if ( tempL[ 0 ] == NULL )
		{
			process();

			// refresh
			for ( int i = 0; i < 38; i++ )
			{
				for ( int j = 0; j < 38; j++ )
				{
					f[ i ][ j ] = 0;
				}
			}

			totalWorks = 0;
		}
		else
		{
			totalWorks += tempL[ 1 ] - 48;
			int lastGoodInd = 3;
			for ( int i = 4; tempL[ i ] != ';'; i++ )
			{
				lastGoodInd++;
			}

			f[ SOURCE ][ ( tempL[ 0 ] - 65 ) ] = tempL[ 1 ] - 48;
			for ( int i = 3; i <= lastGoodInd; i++ )
			{
				f[ ( tempL[ 0 ] - 65 ) ][ FIRSTCMP + tempL[ i ] - 48 ] = tempL[ 1 ] - 48; // here we could assign to 1
				f[ FIRSTCMP + tempL[ i ] - 48 ][ SINK ] = 1;
			}
		}
	}

	return 0;
}

void process()
{
	string toOut = "__________";
	
	int maxFlow = 0;
	int incPath;
	while ( bfs() != 0 )
	{
		incPath = -1;
		for ( int i = SINK; i != SOURCE; i = p[ i ] )
		{
			if ( incPath == -1 )
			{
				incPath = f[ p[ i ] ][ i ];
			}
			else
			{
				incPath = min( incPath, f[ p[ i ] ][ i ] );
			}
		}

		for ( int i = SINK; i != SOURCE; i = p[ i ] )
		{
			f[ p[ i ] ][ i ] -= incPath;
			f[ i ][ p[ i ] ] += incPath;
		}

		maxFlow += incPath;
	}

	if ( maxFlow < totalWorks )
	{
		cout << "!" << endl;
	}
	else
	{
		for ( int i = 0; i <= 25; i++ )
		{
			for ( int j = 26; j <= 35; j++ )
			{
				if ( f[ j ][ i ] == 1 ) // NOTE THAT here f[ i ][ j ] == 0 doesn't work
				{
					toOut[ j - 26 ] = static_cast<char>( ( i % 26 ) + 65 );
				}
			}
		}

		cout << toOut << endl;
	}
}

int bfs() // returns sink plus the augmenting path
{
	int curNode;
	queue<int> q;
	int color[ 38 ];
	
	for ( int i = 0; i < 38; i++ )
	{
		color[ i ] = 0; // 0 is white, 1 is gray
		p[ i ] = -1;
	}

	q.push( SOURCE );
	color[ SOURCE ] = 1;

	while (!q.empty())
	{
		curNode = q.front();
		q.pop();

		for ( int i = 0; i < 38; i++ )
		{
			if ( f[ curNode ][ i ] > 0 && color[ i ] == 0 )
			{
				p[ i ] = curNode;
				color[ i ] = 1;
				if ( i == SINK )
				{
					return SINK; // a positive integer
				}
				q.push( i );
			}
		}
	}

	return 0; // because no vertex has value 0 (vertex numbers start from 1) no problem is with 0
}

Code: Select all

A9 2;
B1 3;

A1 78;
B3 012345689;

A8 169;

A2 89;
B2 0127;

A2 7;

A2 012346789;

A1 2;
B1 169;

A3 125689;

A2 123456789;
B1 02456789;
C5 0124569;
D2 012345789;

A6 01345;
B2 01235689;


A7 01234678;
B3 15;
C1 3579;

A1 0123456789;

A2 029;
B1 12589;
C1 8;
D1 0149;

A3 1678;

A6 03678;

A1 038;
B1 69;

A: 02369;
B1 03456789;

A5 16789;
B1 024567;
C3 013678;

A4 0123456789;
B1 0134568;
C2 123479;

Code: Select all

!
BBB____A__
!
BB______AA
!
AA________
_BA_______
_AA__A____
CAADCCCDBC
!
__________
!
A_________
ABA_D___C_
_A____AA__
!
A_____B___
!
!
AAAAB__C_C