#include <iostream>
using namespace std;

bool used[20];
int matrix[20][20];
int n, result;

bool valid ()
{
	int sum = 0;
	for ( int i = 0; i < n; i++ )
		if ( used[i] )
			sum++;

	return sum < n;
}

int caculate ()
{
	int sum = 0;
	for ( int i = 0; i < n; i++ )
	{
		if ( used[i] )
		{
			for ( int j = 0; j < n; j++ )
				if ( !used[j] )
					sum += matrix[i][j];
		}
	}

	return sum;
}

void search ( int index )
{
	if ( !valid () )
		return;

	if ( index == n )
	{
		result = result > caculate () ? result : caculate ();
		return;
	}

	used[index] = true;
	search ( index + 1 );
	used[index] = false;
	search ( index + 1 );
}

int main()
{
	int i, j;
	scanf ( "%d", &n );
	for ( i = 0; i < n; i++ )
		for ( j = 0; j < n; j++ )
			scanf ( "%d", &matrix[i][j] );
	result = -1;
	search ( 0 );
	printf ( "%d\n", result ); 
	return 0;
}

• 汗死，原来卡了一个常数。。。把一个valid函数去掉反而没有问题了。其实这个本来就没有必要。 (947) yogafrank 2008-10-15 18:54:29