木の上での最大重み独立集合問題

競プロ

入力グラフを木に制限したときの最大重み独立集合問題を解きます．
最大重み独立集合問題はNP困難ですが木に制限すると多項式時間で解けます．

参考元はアルゴリズムデザインのpp.511-513です．

アルゴリズムデザイン

アルゴリズムデザイン

[木の上での最大重み独立集合問題 ]

問題

[入力]

  • 木 T = (V, E)　（ただし、 n = |V|, m = |E| とする）
  • 頂点重み w: V \rightarrow \mathbb{R}_{+}

[出力]
重み和最大の独立集合．
ただし、独立集合とは頂点部分集合 S \subseteq V で、 S のどの2点も辺で結ばれていないもの．

アルゴリズム

任意の頂点 vの部分木 T_{v}を部分問題として動的計画法を使用します．
頂点 rを根とする根付き木を考えます．
任意の頂点 vの部分木 T_{v}に対して以下の2つの部分問題を解きます．

  • vを含む T_{v}の最大重み独立集合．その時の値をdp[v][1]とする．
  • vを含まない T_{v}の最大重み独立集合．その時の値をdp[v][0]とする．

求める答えは max{dp[r][1], dp[r][0]} となります．
vが葉かそうでないかで漸化式を次のように更新します．

（1） v が葉
　　　・ dp[v][0] = 0
　　　・ dp[v][1] = w_{v}

（2） v が葉でない
　　　・dp[v][0] = \sum_{u: vの子} \max(dp[u][0], dp[u][1])
　　　・dp[v][1] = w_v + \sum_{u: vの子} dp[u][0]

時間計算量

各々の頂点や辺を定数回しかみていないので時間計算量は O(n + m) となります．

ソースコード

手元で小さいサンプルしかVerifyしてないです．
（どこかに問題ないかな）

#include <bits/stdc++.h>

using namespace std;

typedef vector<vector<int>> Graph;

// 頂点v（親はp）の部分木に対して問題を解く
void Rec(int p, int v, const Graph &tree, const vector<int> &w, vector<vector<int>> &dp)
{
    if (tree[v].size() == 1) { // vは葉
        dp[v][0] = 0;
        dp[v][1] = w[v];
        return ;
    }

    for (auto u : tree[v])
        if (u != p)
            Rec(v, u, tree, w, dp);

    dp[v][1] = w[v];
    for (auto u : tree[v])
        if (u != p) {
            dp[v][0] += max(dp[u][0], dp[u][1]);
            dp[v][1] += dp[u][0];
        }
}

// 木に制限した最大独立集合問題
int MaximumIndependentSetTree(const Graph &tree, const vector<int> w)
{
    const int n = tree.size();
    vector<vector<int>> dp(n, vector<int>(2, 0));

    Rec( -1, 0, tree, w, dp);

    return max(dp[0][0], dp[0][1]);
}

int main()
{
    ios::sync_with_stdio(false);

    // グラフの入力
    int n;   // 頂点数
    int m;  // 辺数
    int u, v;

    cin >> n >> m;
    Graph tree(n);
    vector<int> w(n);

    for (int i = 0; i < n; ++i)
        cin >> w[i];
    for (int i = 0; i < m; ++i) {
        cin >> u >> v ;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    cout << MaximumIndependentSetTree(tree, w) << endl;

    return 0;
}