変な問題設定。
http://codeforces.com/contest/553/problem/D
問題
N頂点M辺からなる無向グラフが与えられる。
このグラフのうち、いくつかは選択不可な頂点がある。
選択不可な頂点以外からなる頂点の部分集合をSとする。
各頂点のスコアを、(隣接する選択点の数)/(隣接点の数)とし、Sのスコアは、Sに含まれる各頂点のスコアの最小値とする。
スコアが最大化であるSを求めよ。
解法
Sとして(選択不可な頂点を除いた)全頂点を考える。
そこからpriority_queue等を用いて、スコアの低い点を選択から外していけば良い。
(その際、当然隣接点のスコアは再計算する)。
その過程でS内の最低スコアが最大になる状態を更新していく。
int N,M,K; int SS[101010]; bitset<101010> cur,mab; vector<int> E[101010]; double sc[101010]; double ma=-1; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>K; FOR(i,N) cur[i]=1; FOR(i,K) cin>>x, cur[x-1]=0; while(M--) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } set<pair<double,int> > S; FOR(i,N) if(cur[i] && E[i].size()) { FORR(r,E[i]) SS[i]+=cur[r]; sc[i]=SS[i]*1.0/E[i].size(); S.insert({sc[i],i}); } while(S.size()) { auto r=*S.begin(); S.erase(S.begin()); if(ma<r.first) ma=r.first, mab=cur; x=r.second; cur[x]=0; FORR(r2,E[x]) if(cur[r2]) { S.erase({sc[r2],r2}); SS[r2]--; sc[r2]=SS[r2]*1.0/E[r2].size(); S.insert({sc[r2],r2}); } } _P("%d\n",mab.count()); FOR(i,N) if(mab[i]) _P("%d ",i+1); }
まとめ
Div1Dにしては簡単。