SRM 598 div1 hard: TPS - mayoko’s diary

問題

解法

頂点数が 1 の場合を除いて, とりあえず 1 つのビーコンを置く必要があります。最初にビーコンを置いた場所を root にした木で, あと最低いくつのビーコンを置かなければならないか, というように考えます。

ある頂点 v に num 個の子があったとすると, そのうち num-1 個の子より下のどこかに, ビーコンを置かなければならず, 逆に num-1 個のビーコンがあれば, v の下の子頂点はすべて区別出来るようになります(全体の木 - v から下の部分木の部分は, どのみち v より下の頂点では区別できない)。

そこで, dp[v][need] = (頂点 v 以下で, v 以下のどこかにビーコンを置く必要があるかのフラグが need であるような場合に, v より下に置かなければならないビーコンの最低数) とすると, 木 DP が出来ます。

int dp[55][2];

vector<vi> G;
int dfs(int v, int p, int need) {
    int& ret = dp[v][need];
    if (ret >= 0) return ret;
    vector<int> children;
    for (int el : G[v]) if (el != p) children.push_back(el);
    int num = children.size();
    if (num == 0) {
        if (need) return ret = 1;
        else return ret = 0;
    } else if (num == 1) {
        return ret = dfs(children[0], v, need);
    }
    ret = G.size();
    for (int i = 0; i < num; i++) {
        int tmp = 0;
        for (int j = 0; j < num; j++) {
            if (i==j) tmp += dfs(children[j], v, 0);
            else tmp += dfs(children[j], v, 1);
        }
        ret = min(ret, tmp);
    }
    return ret;
}

class TPS {
public:
    int minimalBeacons(vector <string> linked) {
        int n = linked.size();
        G.resize(n);
        for (int i = 0; i < n; i++) {
            G[i].clear();
            for (int j = 0; j < n; j++) {
                if (linked[i][j] == 'Y') G[i].push_back(j);
            }
        }
        int ans = n-1;
        for (int root = 0; root < n; root++) {
            memset(dp, -1, sizeof(dp));
            ans = min(ans, 1+dfs(root, -1, 0));
        }
        return ans;
    }