题目描述
Problem Description
You are given an undirected graph where each edge is either red or black.
Your task is to assign a real number as the 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.
Determine a scheme for assigning these weights.
Input Format
The first line contains two integers $N$ and $M$, representing the number of nodes and edges, respectively.
The nodes are numbered from $1$ to $N$.
The following $M$ lines each contain three integers $a$, $b$, and $c$, describing an edge between nodes $a$ and $b$. If $c$ is $1$, the edge is black; if $c$ is $2$, the edge is red.
Output Format
If a solution exists, output YES on the first line, followed by $N$ integers on the second line representing one possible set of node weights.
Multiple solutions can be output as any one of them.
If no solution exists, output NO on a single line.
Sample Input and Output
Input Sample #1
4 4
1 2 1
2 3 2
1 3 2
3 4 1
Output Sample #1
YES
0.5 0.5 1.5 -0.5
Input Sample #2
2 1
1 2 1
Output Sample #2
YES
0.3 0.7
Input Sample #3
3 2
1 2 2
2 3 2
Output Sample #3
YES
0 2 0
Input Sample #4
3 4
1 2 2
2 2 1
2 1 1
1 2 2
Output Sample #4
NO
Notes
Evaluation Method
Your output is considered correct if and only if:
- The sum of the weights of the two nodes connected by each edge differs from the required sum by no more than $10^{-6}$.
- The sum of the absolute values of all node weights differs from the standard answer by no more than $10^{-6}$.
Data Size and Constraints
This problem uses bundled testing.
- 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 additional constraints.
For $100\%$ of the data, $1 \le N \le 10^5$, $0 \le M \le 2 \times 10^5$.
This problem uses a Special Judge.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分