poj 2531 Network Saboteur 解题报告

题目链接：http://poj.org/problem?id=2531

题目意思：将 n 个点分成两个部分A和B（也就是两个子集啦），使得子集和最大（一定很难理解吧，呵呵）。举个例子吧，对于样例，最佳的分法就是把点2分为一个子集，另一个子集理所当然就是1、3了。 2-1 的权值是50，2-3的权值是40，那么最大就是50+40 = 90了。

首先dfs的话，我不太会做啦。看了队长的用了状态压缩来做，一下子觉得好神奇！！！！

可能第一次接触，理解得不是太深刻，先留着吧。就觉得好神奇，好神奇....好神奇... 不过总觉得它情况判断的时候有重复，看一下第一次的子集1: 1 子集2: 2、3 和第六次的子集1： 2 3 子集2： 1 实质就是一个情况嘛~~~注意：如果一个子集包含n个元素，那意味着另一个子集得0个元素，明显这个是不符合条件的。因为要求得一个子集的所有点对于另一个子集中的所有点（前提是有边相连）的和是最大的！

（不好意思啊，老是逼迫大家看我的恶心涂鸦，不过动手之后真的理解了一些咯，这个是我凭着我的涂鸦来默写滴）

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn =  + ;

 int c[maxn][maxn];

 int A[maxn], B[maxn];  // A[]: 用于保存子集1包含的顶点编号；B[]: 用于保存子集2包含的顶点编号

                      // （注意下标0是表示顶点编号为1的点）

 int main()

 {

     int n;

     while (scanf("%d", &n) != EOF)

     {

         for (int i = ; i < n; i++)

         {

             for (int j = ; j < n; j++)

                 scanf("%d", &c[i][j]);

         }

         int cnt1, cnt2;

         int ans = -;

         for (int i = ; i < (<<n); i++)  // 枚举子集数, n个元素有(2^n - 1)个子集(空集除外)

         {  // （3个元素有七个子集(001~111)

             cnt1 = cnt2 = ;

             for (int j = ; j < n; j++)

             {

                 if (i & ( << j))    // 例如用5(2^0 + 2^2)表示第 1 个点（0）和第3个点（2）被选在第一个子集里

                     A[cnt1++] = j;

                 else

                     B[cnt2++] = j;

             }

              int cursum = ;

              for (int k = ; k < cnt1; k++)

             {

                 for (int j = ; j < cnt2; j++)

                     cursum += c[A[k]][B[j]];

             }

             ans = max(cursum, ans);

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

poj 2531 Network Saboteur 解题报告

最新文章

热门文章