AOJ 2403 The Enemy of My Enemy is My Friend

問題

問題リンク：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2403

解法

頂点に重み付きの価値がついているグラフの最大独立集合を求める問題。

なので枝刈り探索によって解くことができる。具体的な枝刈り方法はwataさんのスライドのp.28以降を参照。

ただし、今回は頂点に重みがついているため「次数1以下は必ず使用」を「次数0は必ず使用」に変更する必要がある。また、グラフ全体が非連結であるケースがあることに注意する。

公式解説

Code

#include <bits/stdc++.h>
using namespace std;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int n;
vector<int> b;
vector<vector<int> > g;
map<string, int> id;
vector<bool> used, visited;

int rec(int v, bool must_use = false){
    int res = b[v];
    visited[v] = true;
    used[v] = true;

    // use v
    vector<int> ls;
    for(auto u : g[v]){
        if(!visited[u]){
            visited[u] = true;
            ls.push_back(u);
        }
    }
    for(int i=0;i<n;i++){
        if(!visited[i]){
            chmax(res, rec(i)+b[v]);
            break;
        }
    }
    for(auto u : ls){
        visited[u] = false;
    }
    // don't use v
    if(ls.size()>0 && !must_use){
        for(int i=0;i<n;i++){
            if(!visited[i]){
                chmax(res, rec(i));
                break;
            }
        }
    }
    visited[v] = false;
    return res;
}

bool solve(){
    cin >> n;
    if(n==0) return false;
    g.clear();
    g.resize(n);
    b.resize(n);
    id.clear();
    used.resize(n);
    visited.resize(n);
    vector<vector<string> > d(n);

    for(int i=0;i<n;i++){
        string s;
        int c;
        cin >> s >> b[i] >> c;
        id[s] = i;
        for(int j=0;j<c;j++){
            string t;
            cin >> t;
            d[i].push_back(t);
        }
    }
    for(int i=0;i<n;i++){
        for(auto s : d[i]){
            g[i].push_back(id[s]);
        }
    }
    cout << rec(0, true) << endl;
    return true;
}

int main(){
    while(solve());
    return 0;
}

コメント

一度探索した連結成分の使用済みフラグをつけるのを忘れていたことにしばらく気が付かなかったので反省