4803080_wa.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/2,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 -1;
			}
		}
	}
	return re;
}
bool dfs(int now,int deep)
{
	if(now>=n) return false;
	if(n-now<deep) return false;
	for(int i=now;i<n;i++)
	{
		used[i]=true;
		if(deep==1)
		{
			int x=get_it();
			if(x>result) result=x;
		}
		else
		{
			dfs(now+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];}
		for(i=1;i<=n-2;i++)
		{
			memset(used,false,sizeof(used));
			dfs(0,i);
		}
		cout<<result<<endl;
	}
	return 0;
}