問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2531思路:
更像是枚舉的搜索，外加一個簡單的對稱性減枝，不過耗時比較久
代碼:
1 #define MAX_NUM 21
2 int matrix[MAX_NUM][MAX_NUM];
3 int mark[MAX_NUM], mark_num;
4 int num, max;
5
6 int
7 calculate()
8 {
9 int i, j;
10 int sum = 0;
11 for(i=0; i<num; i++)
12 if(mark[i]) {
13 for(j=0; j<num; j++)
14 if(!mark[j])
15 sum += matrix[i][j];
16 }
17 return sum;
18 }
19
20 void
21 dfs(int depth)
22 {
23 int rt;
24 if(depth == num) {
25 rt = calculate();
26 max = rt>max ? rt : max;
27 return;
28 }
29 ++mark_num;
30 mark[depth] = 1; /* mark[depth]=1, put 'depth' into the category I */
31 if(mark_num <= (num>>1)) /* pruning */
32 dfs(depth+1);
33 --mark_num;
34 mark[depth] = 0;
35 dfs(depth+1); /* put 'depth' into the category II */
36 }