kmjp's blog

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

2015-2016 ACM-ICPC NEERC : H. Tourist Guide

実装は意外とあっさり。
http://codeforces.com/contest/589/problem/H

問題

N頂点M辺からなる無向グラフがある。
N頂点のうちK頂点注目すべき点が与えられる。

このグラフから、注目すべき点を両端とするパスをできるだけ多くとりたい。
その際以下の条件を満たさなければならない。

  • 1つの注目すべき点は、1個のパスの両端にしかなれない。
  • 1つの辺は、1つのパスでしか利用できない。
  • 言い換えると、同じ点を複数パスが通っても良いし、両端にならないなら注目すべき点でも複数パスが通ってよい。

条件を満たす最多パスの構成を示せ。

解法

各連結成分について、未訪問の適当な頂点からDFSする。
各DFSでは、その子頂点の先にペア未成立の注目すべき点があれば、そこに至るまでのパスをvectorで返す。
未成立の点がある子頂点が複数あれば2個ずつペアにしてパスを構成できるし、今見ている頂点自身も注目すべき点ならそことペアにしても良い。
ペアにならない未成立の点が残るなら、それはDFSの返り値として呼び出しもとに返す。

int N,M,K;
int ok[101010], vis[101010];
vector<int> E[101010];
vector<vector<int> > R;

vector<int> dfs(int cur) {
	vis[cur]=1;
	vector<int> v;
	
	FORR(r,E[cur]) if(vis[r]==0) {
		auto v2=dfs(r);
		if(v2.size()) {
			if(v.size()) {
				v.push_back(cur);
				while(v2.size()) v.push_back(v2.back()), v2.pop_back();
				R.push_back(v);
				v.clear();
			}
			else {
				swap(v,v2);
			}
		}
	}
	
	if(ok[cur] && v.size()) {
		R.push_back(v);
		R.back().push_back(cur);
		v.clear();
	}
	else if(v.size() || ok[cur]) {
		v.push_back(cur);
	}
	return v;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	FOR(i,K) cin>>x, ok[x]=1;
	FOR(i,N) if(vis[i+1]==0) dfs(i+1);
	
	_P("%d\n",R.size());
	FORR(r,R) {
		_P("%d",r.size()-1);
		FORR(rr,r) _P(" %d",rr);
		_P("\n");
	}
}

まとめ

だいぶ考えるけど、わかると面白いタイプの問題。