Codeforces #403 Div1 C. Underground Lab

まぁCにしては簡単だね。
http://codeforces.com/contest/781/problem/C

問題

N頂点の連結グラフが与えられる。
このグラフ上で、K個のパスを作る。
個々のパスはceil(2N/K)個以下の頂点でなければならないとき、すべての頂点がK個のパスの少なくとも1つに含まれるようにしたい。
パスの一例を答えよ。

解法

K個のパス全体で2N個以上の頂点を使うことができる。
よって、まずグラフの全域木を求めよう。
あとはこのグラフを根付き木とみなしてDFSでたどり、通過した点を順に並べると2N個の頂点列ができるので、これをK個に分解すればよい。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

int N,M,K;
vector<int> E[201010];
UF<500000> uf;
vector<int> P;

void dfs(int cur,int pre) {
	P.push_back(cur);
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		P.push_back(cur);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>x>>y;
		if(uf[x]!=uf[y]) {
			uf(x,y);
			E[x].push_back(y);
			E[y].push_back(x);
		}
	}
	
	dfs(1,1);
	
	x=0;
	FOR(i,K) {
		int num=P.size()/K + (P.size()%K>i);
		_P("%d",num);
		FOR(j,num) _P(" %d",P[x++]);
		_P("\n");
	}
	
}

まとめ

まぁ1250ptだしCの割に簡単だね。