POJ - 2531 Network Saboteur解题报告（dfs+剪枝）

题目大意： 好像就是一个学生要干坏事balabala.... 抽象化，给你一个n*n（1-20）的矩阵，矩阵里的每个数c[i][j]<10000。让你想办法将1-n这n个数，分成两组AB，使得∑Cij (i∈A,j∈B)取得最大值。 思路：

枚举所有可能的AB集合划分，2^19≈5 * 10^5;找出这些划分里面的最大值。这样应该是能糊弄过去的。391ms很稳的过去了，但是去查了一下discuss，发现大家都说测试数据很松，而且我也没用到剪枝。

#include<iostream> #include<math.h> using namespace std; int c[25][25]={0}; int a[25]={0}; int b[25]={0}; int numa=1,numb=1; int n; int s=0; /*void ceshi() { cout<<"A:"; for(int i=1;i<numa;i++) { cout<<a[i]; } } */ void dfs(int step) { if(step==n+1) { int t=0; for(int i=1;i<numa;i++) { for(int j=1;j<numb;j++) { t=t+c[a[i]][b[j]]; } } if(s<t)s=t; return; } for(int i=0;i<=1;i++) { if(i==0) { a[numa]=step; numa++; } if(i==1) { b[numb]=step; numb++; } dfs(step+1); if(i==0) { numa--; } if(i==1) { numb--; } } } int main() { cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>c[i][j]; } } dfs(1); cout<<s<<endl; }