問題一覧 > 通常問題

No.1523 +/- Tree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 53
作問者 : NatsubiSoganNatsubiSogan / テスター : aspiaspi nok0nok0 👑 NachiaNachia
0 ProblemId : 5133 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-18 23:27:07

問題文

頂点に 1 から N までの番号がついた N 頂点の重み付き無向木であって、以下の条件をすべて満たすものが存在するか判定し、存在する場合はひとつ構成してください。

  • 各辺について、その重みの絶対値は 109 以下の整数である
  • 辺の重みの総和は正である
  • K 本の辺を通る単純パスが 1 つ以上存在する
  • K 本の辺を通る単純パスの重みは全て負である

入力

N K

  • 入力はすべて整数
  • 2N2000
  • 1KN1

出力

条件を満たす木が存在しないなら、No1 行に出力してください。この場合、2 行目以降には何も出力してはなりません。

存在するなら、まず 1 行目に Yes と出力してください。そして 2 行目から N1 行にわたり以下の形式に従って、構築した木の全ての辺を出力してください。

u1 v1 w1
u2 v2 w2

uN1 vN1 wN1
i+1 (1iN1) 行目の出力は、 i 番目の辺について、頂点 uivi が重み wi で双方向に結ばれていることを表します。ただし、以下の条件をすべて満たさなければなりません。

  • ui,vi,wi は全て整数
  • 1ui,viN
  • 0|wi|109

辺は任意の順番で出力して構いません。

最後に改行してください。

サンプル

サンプル1
入力
4 2
出力
Yes
1 2 2
2 3 -3
3 4 2

解の一例です。

2 本の辺を通る単純パスは、頂点 1,3 間を結ぶものと、頂点 2,4 間を結ぶものです。これらの重みはどちらも 1 (<0) です。また、辺の重みの総和は 1 (>0) です。よって、条件を満たしています。

サンプル2
入力
2 1
出力
No

辺は 1 つだけです。辺の重みが正かつ負などということはあり得ません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。