4803307_ac_1250ms_280k.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
int n;
int map[22][22];
int sum,result;
bool used[22];
int get_it()
{
	int re=sum,i,j;
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if(used[i]==used[j]) 
			{
				re-=map[i][j];
				if(re<=result) return re;
			}
		}
	}
	return re;
}
void testout()
{
	for(int i=0;i<n;i++) cout<<used[i]<<' ';
	cout<<endl;
}
bool dfs(int now,int deep)
{
	if(now>=n) return false;
	if(n-now<deep) return false;
	int x=get_it();
	//testout();
	//cout<<x<<endl;
	if(x>result) result=x;
	for(int i=now;i<n;i++)
	{
		used[i]=true;
		if(deep==1)
		{
			int x=get_it();
			//testout();
			//cout<<x<<endl;
			if(x>result) result=x;
		}
		else
		{
			dfs(i+1,deep-1);
		}
		used[i]=false;
	}
	return false;
}
int main()
{
	int i,j;
	while(cin>>n)
	{
		sum=0;
		result=0;
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
			{cin>>map[i][j];sum+=map[i][j];}
		sum/=2;
		for(i=0;i<=n-1;i++)
		{
			memset(used,false,sizeof(used));
			used[0]=true;
			dfs(1,i);
		}
		cout<<result<<endl;
	}
	return 0;
}