kmjp's blog

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

CSAcademy Round #54 : D. Spanning Trees

途中グダグダだったけど、Gが解けて何とか挽回。
https://csacademy.com/contest/round-54/task/spanning-trees/

問題

2整数N,Kが与えられる。
N頂点の重み付無向グラフで、minimum spanning treeとmaximum spanning treeがそれぞれ一意に定まり、かつK本の辺を共有するグラフを構築せよ。
ただし多重辺は利用できない。

解法

Kが正の場合

まず(K+1)頂点を重さ2の辺K本でつなごう。
これらの辺は両方のtreeで共有する。

残りの頂点に対し、(K+1)本の片方の端から重さ1、反対の端から重さ3の辺を張れば、minimumとmaximumはそれぞれの辺を使うので共有数が増えることはない。

K=0の場合

まず0~(N-1)の頂点を重さ1の辺でつなぎ、minimum spanning treeを作る。
あとはこの辺と多重辺にならないよう、(N-1)本の重さ2の辺でN頂点をつないでいけばよい。
Nと互いに素な整数2以上のMがあれば、i番の頂点と(i+M)番をつないでいくことで達成できる。
N=2,3のときは解がなく、N=1,4,6の場合は別途手作業で結び方を考えよう。

int N,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	vector<vector<int>> V;
	
	cin>>N>>K;
	if(K==0) {
		if(N==1) {
			;
		}
		else if(N==2 || N==3) {
			return _P("-1\n");
		}
		else if(N==4) {
			V.push_back({0,1,1});
			V.push_back({1,2,1});
			V.push_back({2,3,1});
			V.push_back({1,3,2});
			V.push_back({3,0,2});
			V.push_back({0,2,2});
		}
		else if(N==6) {
			V.push_back({0,1,1});
			V.push_back({1,2,1});
			V.push_back({2,3,1});
			V.push_back({3,4,1});
			V.push_back({4,5,1});
			V.push_back({0,2,2});
			V.push_back({2,5,2});
			V.push_back({5,3,2});
			V.push_back({3,1,2});
			V.push_back({1,4,2});
		}
		else {
			for(x=2;x<=N;x++) if(__gcd(x,N)==1) {
				FOR(i,N-1) V.push_back({i,(i+1)%N,1});
				FOR(i,N-1) V.push_back({i,(i+x)%N,2});
				break;
			}
		}
	}
	else {
		FOR(i,K) V.push_back({i,i+1,2});
		for(i=K+1;i<N;i++) {
			V.push_back({0,i,1});
			V.push_back({K,i,3});
		}
	}
	
	_P("%d\n",V.size());
	FORR(v,V) _P("%d %d %d\n",v[0]+1,v[1]+1,v[2]);
}

まとめ

K==0がコーナーケースといえばコーナーケースだけど、そっちの方が悩ましいという問題。