比赛场次 | 84 |
---|---|
比赛名称 | 20110318 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2011-03-18 19:00:00 |
结束时间 | 2011-03-18 22:00:00 |
开放分组 | 全部用户 |
注释介绍 |
题目名称 | 工程规划 |
---|---|
输入输出 | work.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试点数 | 9 评测插件 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
王者自由 | AWWWWWWWWW | 0.000 s | 0.00 MiB | 10 |
绝对零度 | AWWWWWWWWE | 0.000 s | 0.00 MiB | 10 |
ybh | AWWWWWWWWE | 0.000 s | 0.00 MiB | 10 |
Pom | AWWWWWWWWW | 0.000 s | 0.00 MiB | 10 |
苏轼 | C | 0.000 s | 0.00 MiB | 0 |
donny | WWWWWWWWWE | 0.000 s | 0.00 MiB | 0 |
造一幢大楼是一项艰巨的工程,它是由 $n$ 个子任务构成的,给它们分别编号$1,2,\cdots, n(5\leq n\leq 1000)$。由于对一些任务的起始条件有着严格的限制,所以每个任务的起始时间 $T_1,T_2,\cdots,T_n$并不是很容易确定的(但这些起始时间都是非负整数,因为它们必须在整个工程开始后启动)。例如:挖掘完成后,紧接着就要打地基;但是混凝土浇筑完成后,却要等待一段时间再去掉模板。
这种要求就可以用$m(5\leq m\leq 5000)$个不等式表示,不等式形如$T_i- T_j\leq b$代表$i$和$j$的起始时间必须满足的条件。每个不等式的右边都是一个常数 $b$ ,这些常数可能不相同,但是它们都在区间$(-100,100)$ 内。
你的任务就是写一个程序,给定像上面那样的不等式,找出一种可能的起始时间序列$T_1,T_2,\cdots,T_n$,或者判断问题无解。对于有解的情况,要使最早进行的那个任务和整个工程的起始时间相同,也就是说,$T_1,T_2,\cdots,T_n$中至少有一个为 0 。
第一行是用空格隔开的两个正整数$n$和$m$。
接下来 $m$ 行每行有三个用空格隔开的整数 $i,j,b$对应着不等式$T_i- T_j\leq b$。
如果有可行的方案,那么输出$n$行,每行都有一个非负整数且至少有一个为$0$,按顺序表示每个任务的起始时间。
如果没有可行的方案,就输出信息“NO SOLUTION”。
5 8 1 2 0 1 5 -1 2 5 1 3 1 5 4 1 4 4 3 -1 5 3 -3 5 4 -3
0 0 5 4 1
5 5 1 2 -3 1 5 -1 2 5 -1 5 1 -5 4 1 4
NO SOLUTION