← 返回题目列表

Codeforces · 1387/A

A. 图表

中文机器翻译题面 查看原题

给您一个无向图,其中每条边都有两种颜色之一:黑色或红色。

您的任务是为每个节点分配一个实数,以便:

- 对于每个黑色边缘,其端点处的值之和为 $$$1$$$;
- 对于每个红色边缘,其端点处的值之和为 $$$2$$$;
- 所有指定数字的绝对值之和尽可能最小。

否则,如果不可能,则报告没有可行的号码分配。

输入

第一行包含两个整数 $$$N$$$ ($$$1 \leq N \leq 100\,000$$$) 和 $$$M$$$ ($$$0 \leq M \leq 200\,000$$$):分别是节点数和边数。节点由连续整数编号:$$$1、2、\ldots、N$$$。

接下来的 $$$M$$$ 行描述边缘。每行包含三个整数 $$$a$$$、$$$b$$$ 和 $$$c$$$ 表示节点 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a, b \leq N$$$) 之间有一条边,颜色为 $$$c$$$ ($$$1$$$ 表示黑色,$$$2$$$ 表示红色)。

输出

如果有解决方案,第一行应包含单词“YES”,第二行应包含 $$$N$$$ 空格分隔的数字。对于每个 $$$i$$$ ($$$1 \le i \le N$$$),第 $$$i$$$ 个数字应该是分配给节点 $$$i$$$ 的数字。

输出应如下所示:

- 每条边端点处的数字之和与精确值的差异小于$$$10^{-6}$$$;
- 所有指定数字的绝对值之和与最小可能值的差异小于 $$$10^{-6}$$$。

如果有多个有效解,则输出其中任何一个。

如果没有解决方案,则唯一一行应包含单词“NO”。

示例

输入 #1

4 4
1 2 1
2 3 2
1 3 2
3 4 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

3 4
1 2 2
2 2 1
2 1 1
1 2 2

输出#4

NO

注意

评分:
子任务:

1.(5分)$$$N \leq 5$$$,$$$M \leq 14$$$
2.(12 点)$$$N \leq 100$$$
3.(17 点)$$$N \leq 1000$$$
4.(24点)$$$N \leq 10\,000$$$
5.(42分)没有进一步的限制

请注意,在第二个示例中,解不是唯一的。