問題一覧 > 通常問題

No.1523 +/- Tree

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 56
作問者 : NatsubiSogan / テスター : aspi nok0 👑 Nachia
お気に入りにしたユーザー ProblemId : 5133 / 自分の提出
問題文最終更新日: 2021-05-18 23:27:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 297 (順位表) の他の問題:

Problem Statement

Determine whether there exists a weighted undirected tree with $N$ vertices numbered from $1$ to $N$ that satisfies all of the following conditions, and if one exists, construct one.

  • For each edge, its weight is an integer whose absolute value is at most $10^9$.
  • The sum of the edge weights is positive.
  • There exists at least $1$ simple path passing through $K$ edges.
  • The weights of all simple paths passing through $K$ edges are negative.

Input

$N\ K$

  • All input values are integers.
  • $2 \leq N \leq 2000$
  • $1 \leq K \leq N-1$

Output

If no tree satisfying the conditions exists, print No on $1$ line. In this case, nothing must be printed on the $2$nd line or later.

If one exists, first print Yes on the $1$st line. Then, on the $N-1$ lines starting from the $2$nd line, print all edges of the constructed tree in the following format.

$u_1\ v_1\ w_1$
$u_2\ v_2\ w_2$
$\vdots$
$u_{N-1}\ v_{N-1}\ w_{N-1}$
The output on line $i+1\ (1 \leq i \leq N-1)$ indicates that the $i$-th edge bidirectionally connects vertices $u_i$ and $v_i$ with weight $w_i$. All of the following conditions must be satisfied.

  • $u_i,v_i,w_i$ are all integers.
  • $1 \leq u_i,v_i \leq N$
  • $0 \leq |w_i| \leq 10^9$

The edges may be printed in any order.

Print a newline at the end.

Sample

Sample 1
Input
4 2
Output
Yes
1 2 2
2 3 -3
3 4 2

This is one example of a solution.

The simple paths passing through $2$ edges are the one connecting vertices $1,3$ and the one connecting vertices $2,4$. Both of their weights are $-1\ (<0)$. Also, the sum of the edge weights is $1\ (>0)$. Therefore, the conditions are satisfied.

Sample 2
Input
2 1
Output
No

There is only $1$ edge. It is impossible for an edge's weight to be both positive and negative.

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