> // poj 2531 Network Saboteur
> /*
>   求最大,逆向思维，从最小的求。
>   思考：对于花费最大的集合A和B，在A和B各自内部的花费和必然最小，如果不是最小，外部最大花费还可以据需增加的。
>   所以可以求出集合最小内部花费，然后以总花费减去最小花费即可。
> 我是参考这个写出来的，但是不知道为什么我的程序跑了47ms
> */
> #include <stdio.h>
> #include <string.h>
> 
> const bool A = true;
> const bool B = false;
> 
> int c[32][32];
> int in[32], out[32];
> int n, ans, sum, p;
> bool set[32];
> 
> void dfs(int k, int s, int ni, int no) // A B 集合内部最小花费
> {
>     if (s > ans)
>         return;
>     
>     if (k >= n){
>         if (s < ans)
>             ans = s;
>         return;
>     }
>     
>     int t = 0;
>     in[ni] = k;
>     for (int i = 0; i < ni; i++){
>         t += c[in[i]][k];
>     }
>     dfs(k+1, s+t, ni+1, no);
> 
>     t = 0;
>     out[no] = k;
>     for (int i = 0; i < no; i++){
>         t += c[out[i]][k];
>     }
>     dfs(k+1, s+t, ni, no+1);
> 
> }
> 
> int main()
> {
>     scanf("%d", &n);
>     sum = 0;
>     for (int i = 0; i < n ; i++)
>         for (int j = 0; j < n; j++){
>             scanf("%d", &c[i][j]);
>             sum += c[i][j];
>         }
>     sum /= 2;
>     // 取1..n/2 和 1+n/2..n作为一个最小内部花费界限范围
>     p = 0;
>     for (int i = 0; i < n/2; i++){
>         for (int j = 0; j < n/2; j++)
>             p += c[i][j];
>     }
>     for (int i = n/2; i < n; i++){
>         for (int j = n/2; j < n; j++)
>             p += c[i][j];
>     }
>     p /= 2;
>     
>     ans = p;
>     in[0] = 0;
>     dfs(1, 0, 1, 0);
>     
>     printf("%d\n", sum - ans);
>     return 0;
> }