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个元素,明显这个是不符合条件的。因为要求得一个子集的所有点对于另一个子集中的所有点(前提是有边相连)的和是最大的!

 

     

     

      

 

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 20 + 5;
 7 int c[maxn][maxn];
 8 int A[maxn], B[maxn];  // A[]: 用于保存子集1包含的顶点编号;B[]: 用于保存子集2包含的顶点编号
 9                      // (注意下标0是表示顶点编号为1的点)
10 
11 int main()
12 {
13     int n;
14     while (scanf("%d", &n) != EOF)
15     {
16         for (int i = 0; i < n; i++)
17         {
18             for (int j = 0; j < n; j++)
19                 scanf("%d", &c[i][j]);
20         }
21         int cnt1, cnt2;
22         int ans = -1;
23         for (int i = 1; i < (1<<n); i++)  // 枚举子集数, n个元素有(2^n - 1)个子集(空集除外)
24         {  // (3个元素有七个子集(001~111)
25             cnt1 = cnt2 = 0;
26             for (int j = 0; j < n; j++)
27             {
28                 if (i & (1 << j))
29                     A[cnt1++] = j;  
30                 else
31                     B[cnt2++] = j;
32             }
33              int cursum = 0;
34              for (int k = 0; k < cnt1; k++)
35             {
36                 for (int j = 0; j < cnt2; j++)
37                     cursum += c[A[k]][B[j]];
38             }
39             ans = max(cursum, ans);
40         }
41         printf("%d\n", ans);
42     }
43     return 0;
44 }

 

poj 2531 Network Saboteur 解题报告,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。