工程规划

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 work.in 输出文件 work.out
【问题描述】

造一幢大楼是一项艰巨的工程，它是由 n 个子任务构成的，给它们分别编号 1 ， 2 ，…， n(5 ≤ n ≤ 1000) 。由于对一些任务的起始条件有着严格的限制，所以每个任务的起始时间 T 1 ， T 2 ，…， T n 并不是很容易确定的 ( 但这些起始时间都是非负整数，因为它们必须在整个工程开始后启动 ) 。例如：挖掘完成后，紧接着就要打地基；但是混凝土浇筑完成后，却要等待一段时间再去掉模板。
这种要求就可以用 M(5 ≤ m ≤ 5000) 个不等式表示，不等式形如 T i 一 T j ≤ b 代表 i 和 j 的起始时间必须满足的条件。每个不等式的右边都是一个常数 b ，这些常数可能不相同，但是它们都在区间 (-l00 ， 100) 内。
你的任务就是写一个程序，给定像上面那样的不等式，找出一种可能的起始时间序列 T 1 ， T 2 ，…， T n ，或者判断问题无解。对于有解的情况，要使最早进行的那个任务和整个工程的起始时间相同，也就是说， T 1 ， T 2 ，…， T n 中至少有一个为 0 。
【输入】
第一行是用空格隔开的两个正整数 n 和 m ，下面的 m 行每行有三个用空格隔开的整数 i ， j ， b 对应着不等式 T i -T j ≤ b 。
【输出】
如果有可行的方案，那么输出 N 行，每行都有一个非负整数且至少有一个为 0 ，按顺序表示每个任务的起始时间。如果没有可行的方案，就输出信息“ NO SOLUTION ”。
【样例 1 】
work.in
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
work.out
0
0
5
4
1
【样例 2 】
work.in
5 5
1 2 -3
1 5 -1
2 5 -1
5 1 -5
4 1 4
work.out
NO SOLUTION