No.1523 +/- Tree
タグ : / 解いたユーザー数 56
作問者 :
aspi
nok0
👑
Nachia
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もしくは右上の雲マークをクリックしてアカウントを作成してください。