题意：一个集合(矩阵) m[i][j]=m[j][i]权值，分成两个集合，使其权值最大。注：在同一个集合中权值只能算一个。
思路：dfs
代码上需要注意的问题：
for (int i = id + 1; i < n; i++) { if (tmp > data) { dfs(i, tmp); dep[i] = 0; } }
这里有个回溯的操作，如果不执行dfs的话，就说明i放到集合1并不合适，所以放到集合0
解决问题的代码：
#include <iostream> #include <cstdio> #include <string.h> using namespace std; int map[30][30]; int dep[30]; int n, ans; void dfs(int id, int data) { dep[id] = 1; int tmp = data; for (int i = 0; i < n; i++) { if (dep[i] == 0) tmp += map[i][id]; else tmp -= map[i][id]; } if (ans < tmp) ans = tmp; for (int i = id + 1; i < n; i++) { if (tmp > data) { dfs(i, tmp); dep[i] = 0; } } } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &map[i][j]); memset(dep, 0, sizeof(dep)); ans = 0; dfs(0, 0); printf("%d\n", ans); return 0; }
原文：https://www.cnblogs.com/xuxiaojin/p/9405672.html