题目类型 搜索题
题目意思
给出 n 个点 ( 2 <= n <= 20) 和任两点之间边的长度 问怎么划分这 n 个点使划分后得到的两个点集之间的边的权值和最大
例如 1, 2, 3划分后得到 {1,3}和{2}的话 边的权值和就是 边(1,2) + 边(3,2)
解题方法
由于点数较少所以暴力枚举划分后的其中一个点集的情况 这样另一个点集的情况也可知 那么就可以求得边间的权值和 取最大权值和即可
枚举子集可以用DFS
用状态压缩更简单即用 5 (2^0 + 2^2) 表示 第1个点和第3个点 那么总的可能子集情况就是 0 -> 2^n -1
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int m[30][30];
int main() {
int n;
while(scanf("%d", &n) != EOF) {
for( int i=0; i<n; i++ ) {
for( int j=0; j<n; j++ ) {
scanf("%d", &m[i][j]);
}
}
int A[20], B[20];
int ans = 0;
for( int i=1; i<(1<<n); i++ ) { // i 表示枚举的子集
int c1 = 0, c2 = 0;
for( int j=0; j<n; j++ ) { // 求出 i 包含的点有哪些 用c1记录数量 用c2记录另一个点集的数量
if((i & (1<<j))) A[c1++] = j;
else B[c2++] = j;
}
int sum = 0;
for( int j=0; j<c1; j++ ) { // 求权值和
for( int k=0; k<c2; k++ ) {
sum += m[A[j]][B[k]];
}
}
ans = max(ans, sum);
}
printf("%d\n", ans);
}
return 0;
}