UC知道关于pascal一题 工程规划
来源：百度知道 编辑：UC知道 时间：2024/07/06 18:43:31
【问题描述】
造一幢大楼是一项艰巨的工程，它是由n个子任务构成的，给它们分别编号1，2，…，n(5≤n≤1000)。由于对一些任务的起始条件有着严格的限制，所以每个任务的起始时间T1，T2，…，Tn并不是很容易确定的(但这些起始时间都是非负整数，因为它们必须在整个工程开始后启动)。例如：挖掘完成后，紧接着就要打地基；但是混凝土浇筑完成后，却要等待一段时间再去掉模板。
这种要求就可以用M(5≤m≤5000)个不等式表示，不等式形如Ti-Tj≤b代表i和j的起始时间必须满足的条件。每个不等式的右边都是一个常数b，这些常数可能不相同，但是它们都在区间(-100，100)内。
你的任务就是写一个程序，给定像上面那样的不等式，找出一种可能的起始时间序列T1，T2，…，Tn，或者判断问题无解。对于有解的情况，要使最早进行的那个任务和整个工程的起始时间相同，也就是说，T1，T2，…，Tn中至少有一个为0。
【输入】
第一行是用空格隔开的两个正整数n和m，下面的m行每行有三个用空格隔开的整数i，j，b对应着不等式Ti-Tj≤b。
【输出】
如果有可行的方案，那么输出N行，每行都有一个非负整数且至少有一个为0，按顺序表示每个任务的起始时间。如果没有可行的方案，就输出信息“NO SOLUTION”。
【样例1】
work.in work.out
5 8 0
1 2 0 2
1 5 –1 5
2 5 1 4
3 1 5
造一幢大楼是一项艰巨的工程，它是由n个子任务构成的，给它们分别编号1，2，…，n(5≤n≤1000)。由于对一些任务的起始条件有着严格的限制，所以每个任务的起始时间T1，T2，…，Tn并不是很容易确定的(但这些起始时间都是非负整数，因为它们必须在整个工程开始后启动)。例如：挖掘完成后，紧接着就要打地基；但是混凝土浇筑完成后，却要等待一段时间再去掉模板。
这种要求就可以用M(5≤m≤5000)个不等式表示，不等式形如Ti-Tj≤b代表i和j的起始时间必须满足的条件。每个不等式的右边都是一个常数b，这些常数可能不相同，但是它们都在区间(-100，100)内。
你的任务就是写一个程序，给定像上面那样的不等式，找出一种可能的起始时间序列T1，T2，…，Tn，或者判断问题无解。对于有解的情况，要使最早进行的那个任务和整个工程的起始时间相同，也就是说，T1，T2，…，Tn中至少有一个为0。
【输入】
第一行是用空格隔开的两个正整数n和m，下面的m行每行有三个用空格隔开的整数i，j，b对应着不等式Ti-Tj≤b。
【输出】
如果有可行的方案，那么输出N行，每行都有一个非负整数且至少有一个为0，按顺序表示每个任务的起始时间。如果没有可行的方案，就输出信息“NO SOLUTION”。
【样例1】
work.in work.out
5 8 0
1 2 0 2
1 5 –1 5
2 5 1 4
3 1 5
1.20分改程序好像有点少。改程序比写程序困难。
2.下次要叫人帮你改程序最好先说一下你的思路。你中间那一团是floyd么？floyd标准算法好像写错了。标准三循环最外一层是中间变量。。。还有，floyd应该是f推f，not a推f。
感觉此题做法不是图论。你把式子看一下。ai-aj<=c等价于aj>=ai-c。然后我们假设a1＝0，可以推一切aj>=a1-c的式子。然后满足条件的所有j入队。有点类似于spfa思想。（每个i进队一次，出队一次。也可以认为是拓扑排序思想）如果中间推出矛盾，就impossible；没有矛盾就对所有ai排序一下（可能有负值～），输出。
没有想出来floyd怎么做。你说一下你的思路？