luogu#P10733. [NOISG2019 Prelim] Lost Array

    ID: 14670 远端评测题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>2019Special Judge构造NOISG(新加坡)

[NOISG2019 Prelim] Lost Array

题目背景

翻译自 NOISG2019 Prelim B.Lost Array

本题已启用 Special Judge,满足题目条件的任何答案都将视为正确。

题目描述

给定 MM 组形如 min(XAi,XBi)=Ci\min (X_{A_i},X_{B_i})=C_i 的关系式,请构造一个长度为 NN 的数组 XX,使得数组中的每个数字在 1110910^9 之间,并且该数组满足所有的关系式。

题目保证数组存在。

输入格式

第一行两个整数 N,MN,M

接下来 MM 行,每行三个数字 Ai,Bi,CiA_i,B_i,C_i

输出格式

共一行 NN 个整数,代表你构造的数组 XX

2 1
2 1 7
9 7
5 6
1 2 1
3 5 4
1 5 3
1 3 3
2 3 1
2 4 1
3 1 4 1 5
2 5
1 2 1
2 1 1
1 2 1
1 2 1
2 1 1
1 114514
5 1
1 2 123
123 1000000000 3 4 26311337

提示

【样例 #1 解释】

显然,min(X2,X1)=min(9,7)=7\min (X_2,X_1) = \min (9,7) =7,满足题目条件。

【样例 #3 解释】

原题的题面没有此样例,但测试数据有。

第一个限制为 min(X1,X2)=1\min (X_1,X_2) =1,所有的条件实际上和这个限制一样。

【样例 #4 解释】

唯一的限制为 min(X1,X2)=123\min (X_1,X_2) =123,其余的数字可以是介于 1110910^9 之间的任何数字。

【数据范围】

Subtask\text{Subtask} 分值 特殊性质
00 样例
11 55 N=2,M=1N=2,M=1
22 66 M3M\leq 3
33 2020 N,M1000N,M\leq 1000
44 2121 Ci10,N5C_i \leq 10,N \leq 5
55 4848

对于 100%100\% 的数据:

  • 1N,M1051 \leq N,M \leq 10^5
  • 1Ai,BiN1 \leq A_i ,B_i \leq N
  • AiBiA_i \neq B_i
  • 1Ci1091 \leq C_i \leq 10^9