[BalticOI 2020 Day2] 图

题目描述

你有一个无向图，每条边都有一种颜色：红或者黑。你要做的就是为每个节点配一个实数点权，使得： - 对于每条黑色边，两个端点的点权之和为 $1$ - 对于每条红色边，两个端点的点权之和为 $2$ - 所有点权的绝对值之和是最小的求一种点权的分配方案。

输入输出格式

输入格式

第一行两个整数 $N,M$ 代表点数和边数。所有点的编号为 $1$ 到 $N$。接下来 $M$ 行每行三个整数 $a,b,c$ 描述一条边端点为 $a$ 和 $b$，如果 $c$ 是 $1$ 那么这条边是黑色边，如果 $c$ 是 $2$ 那么这条边是红色边。

输出格式

如果有解，首先第一行输出 `YES`，然后第二行 $N$ 个整数代表可能的一组点权。多组解输出任意一组即可。如果无解，一行一个字符串 `NO`。

输入输出样例

输入样例 #1

输出样例 #1

YES
0.5 0.5 1.5 -0.5

输入样例 #2

2 1
1 2 1

输出样例 #2

YES
0.3 0.7

输入样例 #3

3 2
1 2 2
2 3 2

输出样例 #3

YES
0 2 0

输入样例 #4

输出样例 #4

NO

说明

#### 评测方式您的输出被评判为正确，当且仅当： - 每条边所连两点的点权和与该边要求的点权间的误差不超过 $10^{-6}$。 - 所有点权的绝对值之和与标准答案误差不超过 $10^{-6}$。 #### 数据规模与约定 **本题采用捆绑测试。** - 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）：无特殊限制。对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le M \le 2 \times 10^5$。 **本题使用 Special Judge。**