kmjp's blog

競技プログラミング参加記です

Codeforces ECR #054 : D. Edge Deletion

まんまとはまってしまった。
http://codeforces.com/contest/1076/problem/D

問題

コスト付の辺をもつN頂点の根付きの無向グラフが与えられる。
このうちK辺だけを残すとき、根と連結した頂点のうち根からの距離が元のグラフを一致するものの数を最大化したい。
辺の残し方の一例を答えよ。

解法

K辺を使えばmin(N,K+1)個の頂点について条件を満たすことができるのは想像がつく。
MSTを取ってしまうとダメで、ダイクストラ法を行い遷移元との辺を残すようにしよう。

int N,M,K;
int X[303030],Y[303030],W[303030];
vector<pair<int,int>> E[303030];
ll D[303030];
int from[303030];
set<int> ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&N,&M,&K);
	FOR(i,M) {
		scanf("%d%d%d",&x,&y,&r);
		X[i]=x-1;
		Y[i]=y-1;
		W[i]=r;
		E[x-1].push_back({y-1,i});
		E[y-1].push_back({x-1,i});
	}
	
	FOR(i,N) D[i]=1LL<<60;
	D[0]=0;
	priority_queue<pair<ll,int>> Q;
	Q.push({0,0});
	while(ret.size()<K && Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		
		if(D[cur]!=co) continue;
		
		if(cur) ret.insert(from[cur]+1);
		FORR(e,E[cur]) if(D[e.first]>D[cur]+W[e.second]) {
			D[e.first]=D[cur]+W[e.second];
			from[e.first]=e.second;
			Q.push({-D[e.first],e.first});
		}
	}
	
	cout<<ret.size()<<endl;
	FORR(e,ret) cout<<e<<" ";
}

まとめ

本番まんまとMSTを取ってしまった…。