途中グダグダだったけど、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がコーナーケースといえばコーナーケースだけど、そっちの方が悩ましいという問題。