【题解】HackerRank - Demanding Money

Posted on In Disqus:

题目

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;
}