P6696 [BalticOI 2020] Graph (Day2)

You have an undirected graph, and each edge has a color: red or black. What you need to do is assign a real-valued weight to each node such that: - For every black edge, the sum of the weights of its two endpoints is $1$. - For every red edge, the sum of the weights of its two endpoints is $2$. - The sum of the absolute values of all node weights is minimized. Find one such assignment of node weights.

The first line contains two integers $N, M$, representing the number of nodes and the number of edges. The nodes are numbered from $1$ to $N$. The next $M$ lines each contain three integers $a, b, c$, describing an edge whose endpoints are $a$ and $b$. If $c$ is $1$, then this edge is black; if $c$ is $2$, then this edge is red.

If there is a solution, first output `YES` on the first line, then output $N$ integers on the second line representing one possible set of node weights. If there are multiple solutions, output any one of them. If there is no solution, output a single line containing the string `NO`.

#### Judging Method Your output is considered correct if and only if: - For every edge, the error between the sum of the weights of its two endpoints and the required value for that edge is at most $10^{-6}$. - The error between the sum of the absolute values of all node weights and the standard answer is at most $10^{-6}$. #### Constraints and Notes **This problem uses bundled testdata.** - Subtask 1 (5 pts): $N \le 5$, $M \le 14$. - Subtask 2 (12 pts): $N \le 100$. - Subtask 3 (17 pts): $N \le 1000$. - Subtask 4 (24 pts): $N \le 10^4$. - Subtask 5 (42 pts): no special restrictions. For $100\%$ of the testdata, $1 \le N \le 10^5$, $0 \le M \le 2 \times 10^5$. **This problem uses a Special Judge.** Translated by ChatGPT 5