ナップサック問題 [Kyoto University Programming Contest 2019 B]

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_b

前提知識

• UnionFind
• DP

解説

https://atcoder.jp/contests/kupc2019/submissions/7956197

ナップサック問題の派生であるが、追加されてる条件について考えてみる。
aとbを一緒に入れる必要があり、bとcも一緒に入れる必要があるとき、a,b,cはすべて一緒に入れる必要がある。
このように連結関係にあれば、すべて入れる必要があり、1つの荷物とみなすことができる。
よって、連結成分をUnionFindでまとめて、1つの荷物にしてからナップサック問題を解こう。

ナップサック問題はDPで解ける。
dp[i][wei] := i番目の荷物までを使って重さweiを作る時の合計価値の最大値

int N, M, W, w[101], v[101];
int dp[101][10101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> W;
    rep(i, 0, N) cin >> w[i] >> v[i];

    UnionFind uf(N);
    rep(i, 0, M) {
        int a, b; cin >> a >> b; 
        a--; b--;
        uf(a, b);
    }

    vector<int> items;
    rep(i, 0, N) {
        if (uf[i] != i) {
            w[uf[i]] += w[i];
            v[uf[i]] += v[i];
        }
        else items.push_back(i);
    }

    N = items.size();
    rep(i, 0, N + 1) rep(wei, 0, W + 1) dp[i][wei] = -inf;
    dp[0][0] = 0;
    rep(i, 0, N) rep(wei, 0, W) {
        chmax(dp[i + 1][wei], dp[i][wei]);
        int wei2 = wei + w[items[i]];
        if (wei2 <= W) chmax(dp[i + 1][wei2], dp[i][wei] + v[items[i]]);
    }

    int ans = -infl;
    rep(wei2, 0, W + 1) chmax(ans, dp[N][wei2]);
    cout << ans << endl;
}