1112.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <vector>
#include <algorithm>
#include <stdio.h>
#include <memory.h>
#include <math.h>

using namespace std;

vector<int> unknow[100];
vector< pair<int,int> > s;

int sign[100];
bool e[100][100];
int flag[110][110];

int a, b, an, bn;

bool search( int k, int key )
{
	int i;

	sign[k] = key;

	if( key == a ) an++;
	else bn++;

	for( i=0; i<unknow[k].size(); i++ )
		if( sign[ unknow[k][i] ] == 0 )
		{
			if( !search( unknow[k][i], a+b-key ) ) 
				return false;
		}
		else if( sign[ unknow[k][i] ] == key ) 
			return false;

	return true;
}


int main()
{
	int n, i, j, k, x, y;

	scanf( "%d", &n );

	for( i=0; i<n; i++ )
	for( j=0; j<n; j++ )
		e[i][j] = ( i == j );

	for( i=0; i<n; i++ )
	{
		unknow[i].clear();
		while( 1 )
		{
			scanf( "%d", &j );
			if( j == 0 ) break;
			j--;
			e[i][j] = true;
		}
	}

	for( i=0; i<n; i++ )
	for( j=0; j<n; j++ )
		if( !e[i][j] || !e[j][i] ) unknow[i].push_back( j );
	

	memset( sign, 0, sizeof(sign) );
	memset( flag, 0, sizeof(flag) );

	a = 1, b = 2;

	s.clear();
	for( i=0; i<n; i++ )
		if( sign[i] == 0 )
		{
			
			an = bn = 0;
			if( !search( i, a ) ) break;

			s.push_back( pair<int,int>( an, bn ) );
			a += 2, b += 2;
		}

	if( i < n )
	{
		printf( "No solution\n" );
		return 0;
	}

	flag[0][0] = true;

	for( k=0; k<s.size(); k++ )
	for( i=n-1; i>=0; i-- )
	for( j=n-1; j>=0; j-- )
		if( flag[i][j] != 0 )
		{
			if( ( x = s[k].first+i ) < n && ( y = s[k].second+j ) < n && !flag[x][y] )
				flag[x][y] = k+1;
			if( ( x = s[k].first+j ) < n && ( y = s[k].second+i ) < n && !flag[y][x] )
				flag[y][x] = -(k+1);
		}

	x = 0; y = n;
	for( i=1; i<n; i++ )
		if( flag[i][n-i] != 0 && abs( i*2-n ) < y )
			x = i, y = abs( i*2-n );

	y = n-x;

	vector< int > s1,s2;

	while( x || y )
	{
		k = abs( flag[x][y] ) - 1;
		a = k*2+1; b = k*2+2;

		if( flag[x][y] < 0 ) swap( a, b );

		for( i=0; i<n; i++ )
			if( sign[i] == a )
				s1.push_back( i+1 );
			else if( sign[i] == b )
				s2.push_back( i+1 );

		a = s[k].first, b = s[k].second;
		if( flag[x][y] < 0 ) swap( a, b );

		x -= a, y-=b;
	}

	printf( "%d", s1.size() );
	for( i=0; i<s1.size(); i++ )
		printf( " %d", s1[i] );
	printf( "\n" );

	printf( "%d", s2.size() );
	for( i=0; i<s2.size(); i++ )
		printf( " %d", s2[i] );
	printf( "\n" );

	return 0;
}