POJ-2531 Network Saboteur (DFS)

题目链接：点击打开链接

题意：

给你结点之间的权值，让你把结点分成两组， 让两组结点之间即权值之和最小。

思路：

没想到是这样一种暴力dfs题，先把每个结点都设为a组，然后通过不断的回溯来枚举所有情况。

代码如下：

 

#include <iostream> #include <string.h> using namespace std; int n; int g[21][21]; int a[21], b[21], mx = 0; bool vis[21]; void dfs(int x) { if(x == n+1) { int num1 = 0, num2 = 0; for(int i = 1;i <= n;i++) if(vis[i]) a[num1++] = i; else b[num2++] = i; int sum = 0; for(int i = 0;i < num1;i++) for(int j = 0;j < num2;j++) sum += g[ a[i] ][ b[j] ]; mx = max(mx,sum); return; } vis[x] = true; dfs(x+1); vis[x] = false; dfs(x+1); } int main() { cin>>n; for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) cin>>g[i][j]; dfs(1); cout<<mx<<endl; return 0; }