0%

【题解】HackerRank - Demanding Money

题目

https://www.hackerrank.com/challenges/borrowing-money/problem

题意

无向图上每个结点有个权值,求权最大的独立集的权及其方案数。

题解

  • 对于一般图的最大独立集,是 NPC 问题,题目中 n 也很小,所以搜索。
  • 这个问题中要求输出方案数,但是如果有很多的孤立点,那么方案数会很大 ($2^k$)。由于要统计方案数,一个一个数即便是有剪枝也会超时(因为孤立点的值可以为 0)。
  • 对于所有孤立点单独考虑,如果孤立点值不为 0,那么肯定要选,答案乘上权值,如果值为 0,那么计数要乘 2。
  • 剔除所有孤立点进行搜索,现在联通块的大小至少为 2,枚举所有取法不剪枝,那么在所有联通块大小均为 2 时,复杂度为 $O(2^{n/2})$,可以接受。
  • 官方题解是 meet-in-the-middle,实现起来比较繁琐,也不见得快。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 34 + 5;
int w[maxn], n, m, ans, cnt;
bool G[maxn][maxn], vis[maxn];

void go(int k, int s) {
if (k == n) {
if (s < ans) return;
if (s > ans) { ans = s; cnt = 0; }
++cnt;
return;
}
go(k + 1, s);
if (vis[k]) return;
bool f = true;
FOR (i, 0, k)
if (G[k][i] && vis[i]) { f = false; break; }
if (f) {
vis[k] = 1;
go(k + 1, s + w[k]);
vis[k] = 0;
}
}

int main() {
cin >> n >> m;
FOR (i, 0, n) scanf("%d", &w[i]);
FOR (_, 0, m) {
static int u, v;
scanf("%d%d", &u, &v);
--u; --v;
G[u][v] = G[v][u] = 1;
}
LL add = 0, mul = 1;
FOR (i, 0, n) {
bool f = 1;
FOR (j, 0, n) if (G[i][j]) { f = 0; break; }
if (f) {
if (w[i]) add += w[i];
else mul <<= 1;
vis[i] = 1;
}
}
go(0, 0);
cout << ans + add << ' ' << cnt * mul << endl;
}