mayoko’s diary

プロコンとかいろいろ。

SRM 644 div2 hard:TreeCutting

典型っぽい(解けるとは言っていない)。

問題:木のグラフが与えられる。グラフの頂点のいくつかには数字が書いてあって,以下の条件を満たすように木を辺の切断によってグループ分けしたい。
・数字の書いてある頂点が同じグループになってはいけない。
・各グループの個数は数字の書いてある頂点と同じ数になる。
この条件を満たすことは可能か。

解法:ある辺で切断すると、グラフは2つに分かれる。この時の頂点数をA,Bとすると、それぞれの頂点以下でグラフが何個の頂点を持っていなければならないかはわかるので、その通りに頂点があるかを調べる。
このような辺のわけかたがグラフを分割する数分だけあれば解が存在する。
以下ソースコード

const int MAXN = 64;
vector<int> G[MAXN];
vector<int> NN;
int size[2][MAXN]; // 0:自分以下にある頂点数 1:目標とする頂点数

void dfs(int v, int p) {
    size[0][v] = 1;
    if (NN[v] != -1) size[1][v] = NN[v];
    for (int next : G[v]) {
        if (next == p) continue;
        dfs(next, v);
        size[0][v] += size[0][next];
        size[1][v] += size[1][next];
    }
}

bool ok(int a, int b) {
    for (int i = 0; i < MAXN; i++) size[0][i] = size[1][i] = 0;
    dfs(a, b);
    dfs(b, a);
    return (size[0][a] == size[1][a]) && (size[0][b] == size[1][b]);
}

class TreeCutting {
public:
    string can(vector <int> par, vector <int> num) {
        for (int i = 0; i < MAXN; i++) G[i].clear();
        const string YES = "POSSIBLE", NO = "IMPOSSIBLE";
        NN = num;
        int cnt = 0, target = 0, n = num.size();
        for (int i = 0; i < n; i++) if (num[i] != -1) target++;
        for (int i = 0; i < n-1; i++) {
            G[par[i]].push_back(i+1);
            G[i+1].push_back(par[i]);
        }
        for (int i = 0; i < n-1; i++) {
            if (ok(par[i], i+1)) cnt++;
        }
        if (cnt == target-1) return YES;
        else return NO;
    }
};