题意分析

有一个无向图，现在，我们需要将无向图进行划分，是的，每两个点之间都有连边，并且两边集合的点之间边有权值，集合内的点之间没有权值，现在求最大的情况是多少 。

解题思路

这是一道非常新颖的DFS的思路，我们需要做的就是穷尽所有的可能情况： 1.我们首先假设，所有的点都在$0$集合 2.我们穷举的情况是，所有的点在$0,1$之间的分布 3.在DFS中，我们不断的维护最大值就好了 我们穷举所有的情况的过程中，要动态的维护一个book全局变量，我们在DFS中的搜索顺序是将所有的的点不管是不是属于$1$集合，我们都默认的将其加入$1$集合，然后再反向回溯从而枚举素有的情况

C++代码实现

cpp

#include"iostream"
#include"cstdio"
#include"cstdlib"
#include"cstring"
#define N 23
 
using namespace std;
 
int map[N][N];
int n;
bool book[N];   //判断是在0,1中 
int sum=0;
 
void dfs(int p,int ans)
{
	book[p]=1;
	int count=ans;
	for(int i=1;i<=n;i++)
	{
		if(book[i]==1) count-=map[p][i];
		else count+=map[p][i]; 
	}
	if(count>sum) sum=count;
	for(int i=p+1;i<=n;i++)
	{
		dfs(i,count);
		book[i]=0;
	}
}
 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) scanf("%d",&map[i][j]);
	}
	memset(book,0,sizeof(book));
	
	dfs(1,0);
	printf("%d\n",sum);
	return 0;
}