PKU 2732 Countdown
http://poj.org/problem?id=2732
家系図が与えられる。
d回子供をたどって到達する人数の多いほうから3人ほど答えろというような問題。
やるだけ。
map<string,int> stoi; vector<string> itos; int get(string& a){ if(stoi.count(a)) return stoi[a]; stoi[a] = SZ(itos); itos.pb(a); return SZ(itos)-1; } vector<int> G[1000]; int dfs(int p,int d){ if(d==0) return 1; int ret=0; FOR(it,G[p]) ret += dfs(*it,d-1); return ret; } void solve(int ca){ if(ca) cout<<endl; printf("Tree %d:\n",ca+1); stoi.clear(); itos.clear(); int n,d; cin>>n>>d; rep(i,1000) G[i].clear(); rep(i,n){ string p; cin>>p; int pi=get(p); int m; cin>>m; rep(j,m){ cin>>p; int c=get(p); G[pi].pb(c); } } vector<pair<int,string> > ans; rep(i,1000){ int g=dfs(i,d); if(g) ans.pb(mp(-g,itos[i])); } sort(ALL(ans)); rep(i,SZ(ans)){ if(i>=3 && ans[i].F!=ans[i-1].F) break; cout<<ans[i].S<<' '<<-ans[i].F<<endl; } } main(){ int t; cin>>t; rep(i,t) solve(i); }