AOJ 2480 : Blame Game
問題リンク : Blame Game | Aizu Online Judge
問題概要 :
Alice と Bob は互いを攻め合いたい
Alice は n 個の欠点があり、
Bob は m 個の欠点がある
ある欠点は 0 個以上の相手の欠点と関係があり、その関係は双方向に成り立つ
Alice と Bob は交互に相手の欠点を攻める
ただし、同じ欠点は高々1回までしか攻めれない
Alice が最初に Bob の欠点の1つを選び攻める
Bob は先ほど攻められた欠点と関係のある Alice の欠点を1つ選び、そこを攻める
Alice は先ほど攻められた欠点と関係ある Bob の欠点を1つ選び、そこを攻める
こうしてお互いを攻め合い、関係のある欠点を見つけれず攻めることのできなくなった方が歯医者となる
勝利するのはどちらか
解法 :
欠点の関係は2部グラフになる
2部グラフの最大マッチングを求め、それが m と等しければ Bob の勝ち
それ以外であれば Alice の勝ち
最大マッチングが m と等しい時 Bob が勝つ
-> Aliceがどれか1つノードを選ぶとBobは最大マッチングの結果にしたがってそれと対応したノードを必ず1つは選べる
もしBobが選んだノードから辺がなければBobの勝利だし、
そうでなければAliceが先ほどBobが選んだノードに隣接するノードを選ぶ
すると先ほどと同様にBobは最大マッチングの結果に従って対応するノードを必ず1つは選べる
以上を繰り返し最終的にBobが勝つ
( 以下 intuitive )
そうでない場合、
最大マッチングはmと等しくない
このとき、2つの状況が考えられる
1. BobのノードとつながっていないAliceのノードが存在する
=> この時、Aliceはそのノードを選べば勝利
2. Bobのある2つのノードについて、片方を選ぶともう片方が選べなくなるような関係が存在する
=> この時、Aliceはまず最初にその2つのノードのいずれかを選び、
Bobはそれに対応したノードを選ぶ
次にAliceが先ほど選ばなかったほうのノードを選べばAliceの勝ち
o---x1 こんな感じで,x1を選べばx2が選べないし、
\--x2 x2を選べばx1を選べないような場所が必ずでてくる、ないなら全てマッチングされてしまうはずで最大マッチングがmでないという条件に反する
よってAliceが勝つ
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; const int MAX_V = 1100; int n,m,k,b,V; vector<int> G[MAX_V]; int match[MAX_V]; bool used[MAX_V]; void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } bool dfs(int v){ used[v] = true; rep(i,G[v].size()){ int next = G[v][i]; if( match[next] < 0 || ( !used[match[next]] && dfs(match[next]) ) ) { match[v] = next; match[next] = v; return true; } } return false; } int bipartite_matching() { int matching = 0; memset(match,-1,sizeof(match)); rep(i,n) if( match[i] < 0 ) { memset(used,0,sizeof(used)); if( dfs(i) ) ++matching; } return matching; } int main(){ scanf("%d %d",&n,&m); rep(i,n){ scanf("%d",&k); rep(j,k){ scanf("%d",&b); --b; add_edge(i,n+b); } } puts((bipartite_matching()==m)?"Bob":"Alice"); return 0; }