yukicoder : No.479 頂点は要らない

久々のyukicoderは幸先のよいスタートが切れました。
http://yukicoder.me/problems/no/479

問題

N頂点M無向辺からなるグラフが与えられる。

頂点を買い取ると、その頂点につながる辺をセットですべて買い取ることができる。
各頂点は0～(N-1)の番号が振られており、i番の頂点を買い取るコストは2^iである。

このグラフにおけるすべての辺を買い取りたい。
その際の最小コストを求めよ。

解法

問題文を言い換えると、各辺に対し両端の頂点の少なくとも片方は買い取るようにすればよい。
今回の買い取りコストの特徴として、i番の頂点を買うコストはi番未満の頂点をすべて買うコストより高い。
よって、貪欲に高い頂点を買わないようにしていけばよい。

頂点番号iの大きな順に、以下をチェックしていけばよい。

• 隣接点のうち、iより番号が大きく未購入の点が1個でもあるなら、(ここでi番の点を買わないとその接続辺は買われなくなってしまうので)i番の点を買う。

int N,M;
int need[101010];
vector<int> E[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[min(x,y)].push_back(max(x,y));
	}
	for(i=N-1;i>=0;i--) FORR(e,E[i]) if(need[e]==0) need[i]=1;
	
	int first=1;
	for(i=N-1;i>=0;i--) {
		if(need[i]==0 && first==1) continue;
		first=0;
		_P("%d",need[i]);
	}
	_P("\n");
}

まとめ

以前SRMで頂点のコストが3^iな問題があったのを思い出した。