Benelux Algorithm Programming Contest 2016 C Brexit
問題
N個の国と、P個の友好関係があります。
自分の国はXです。今、ある団体からLという国が脱退することを表明したので、回りの国も脱退するかどうかを考えています。
ある国は、友好関係を結んでいる国のなかで半分以上が脱退を表明していたら、その国も脱退することを表明します。
自分の国が脱退することになるかどうかを判定してください、という問題です。
解法
着火地点であるLから順番に幅優先探索で見ていきます。
現在見ている、脱退を決めた国をYとします。Yと友好関係を結んでいる国をすべて調べ、まだ脱退を表明していない国があったら、Yの国の分だけカウントを増やします。そして、その国が半数を超えたら、あらたに脱退を表明した国として、キューに挿入します。
キューがすべてなくなるか、自分の国が脱退を表明した時点で探索を切り上げ、答えを出力します。
既に脱退を表明して処理を行ったかどうかのメモをするあたりがポイント…かなと思います。
提出コードは以下になります。
#include <bits/stdc++.h> using namespace std; struct data { bool used; int sum; int num; vector<int> v; }; void prians(bool answer) { if(answer) cout << "leave" << endl; else cout << "stay" << endl; } bool solve(); int c, p, x, l; data memo[200005]; queue<int> qu; int main() { int i, a, b; scanf("%d %d %d %d", &c, &p, &x, &l); --x; --l; for(i = 0; i < c; ++i) { memo[i].sum = memo[i].num = 0; memo[i].used = 0; } for(i = 0; i < p; ++i) { scanf("%d %d", &a, &b); --a; --b; ++memo[a].sum; ++memo[b].sum; memo[a].v.push_back(b); memo[b].v.push_back(a); } prians(solve()); return 0; } bool solve() { int now, i, nextn; qu.push(l); memo[l].used = 1; while(qu.size() > 0 && (!memo[x].used)) { now = qu.front(); qu.pop(); for(i = 0; i < memo[now].v.size(); ++i) { nextn = memo[now].v[i]; ++memo[nextn].num; if(((memo[nextn].sum + 1) / 2 <= memo[nextn].num) && (!memo[nextn].used)) { memo[nextn].used = 1; qu.push(nextn); } } } return memo[x].used; }