yukicoder : No.1523 +/- Tree

色々解法がありそう。
https://yukicoder.me/problems/no/1523

問題

整数N,Kが与えられる。
以下のグラフを構成せよ。

• N頂点の木を成す無向グラフで、辺には整数の重みがある。
• 長さKのパスが1つ以上あり、それらはいずれも辺の重みの総和が負
• 全辺の重みの総和は正

解法

• K=N-1の時解なし
• K=2の時
  • Nが偶数、すなわち辺の数が奇数の時、全点を1列に並べて、奇数番目の辺をinf-1、偶数番目の辺を-inf程度の重みにすればよい。
  • Nが奇数、すなわち辺の数が偶数の時解なし
• K=3以上N-2以下の時
  • ほうき型のグラフを作ろう。まずK頂点で長さ(K-1)のパスを作る。それらは重みの合計が-infとなるようにする。
  • 残りの点をすべて上記パスの端から生やす。その重みはinf-1とする。
  • こうすると長さKのパスの重みは-1となるが、重み(inf-1)の辺は2本以上あるので全体の重みの総和は正となる。

int N,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	
	if(K==2&&N%2==0) {
		cout<<"Yes"<<endl;
		FOR(i,N-1) {
			if(i%2==0) {
				cout<<(i+1)<<" "<<(i+2)<<" "<<100000<<endl;
			}
			else {
				cout<<(i+1)<<" "<<(i+2)<<" "<<-100001<<endl;
			}
		}
		
	}
	else if(K<=2||K==N-1) {
		cout<<"No"<<endl;
	}
	else {
		cout<<"Yes"<<endl;
		FOR(i,K-1) {
			cout<<(i+1)<<" "<<(i+2)<<" "<<-100000<<endl;
		}
		for(i=K+1;i<=N;i++) {
			cout<<K<<" "<<(i)<<" "<<(100000*(K-1)-1)<<endl;
		}
	}
	
}

まとめ

Editorialよりシンプルだと思うけどどうだろう。