実装は意外とあっさり。
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"); } }
まとめ
だいぶ考えるけど、わかると面白いタイプの問題。