当前位置:首页 > 差分约束 > 正文
洛谷P1260工程规划
4045+

题目大意:一项工程有n个子任务,任务之间在时间上有先后关系,什么时间该开始什么任务呢?

题目描述

造一幢大楼是一项艰巨的工程,它是由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:

5 8
1 2 0
1 5 –1
2 5 1
3 1 5
4 1 4
4 3 –1
5 3 –1
5 4 –3

输出样例#1:

0
2
5
4
1

输入样例#2:

5 5
1 2 –3
1 5 –1
2 5 –1
5 1 –5
4 1 4

输出样例#2:

NO SOLUTION

解题思路

两个未知数的差小于等于某个常数(大于等于也可以,因为左右乘以-1就可以化成小于等于),这样的不等式组就称作差分约束系统,差分约束可以转化成求最短路径。

如Ti-Tj≤b,即Ti≤Tj+b,与求最短路很相似,建立j到i的一条有向边,权值为b,这样,到i的距离越短越不会出问题。对于所有的约束关系,都建立一条有向边,然后求最短路径,求完后,必定满足所有约束条件(如果不满足,会继续进行松弛操作,从而更新Ti的最短路径,使得Ti≤Tj+b);如果求不完,即出现负环,那么输出“NO SOLUTION”。

如何判断负环呢?如果用SPFA求最短路径,那么一个点重复入队超过n次就说明出现负环(松弛次数);如果用深搜求最短路径,那么一路搜下去,搜回自己或者搜到访问过的点,就是出现负环。

首先介绍一下SPFA的做法:首先是建图,把差分约束系统中的所有不等式都转换成图中的边(边权可以是负数),然后求单源最短路径。这个单源是谁呢?我们可以建立一个源点0(如果0被用了,可以用n+1、n+2等编号),然后从源点向其他各点连一条权值为0的有向边(Ti<=T0+0),代表其他子任务可以同时开始做,然后从源点跑一遍SPFA求单源最短路径,最后可能出现负数时间,让所有时间都减去最小的那个时间,就能让最小的时间从0开始了。求完后,发现这个超级源点也没什么用,实际上他根问题本身没有任何关系,至少让各个任务编号可以入队而已,因此,我们也可以手动把所有子任务的点入队,直接进行松弛操作,二不要这个超级源点。

接着介绍一下判断负环的方法:如果出现负环,一个点需要重复入队n次,就好像跑了n次的SPFA一样,时间复杂度是O(kmn),如果n和m都超过10000,那么很容易超时的!还有一种方案就是深搜判断负环,不用SPFA也不用队列了,直接依次搜索n个点,循环这n个点到其他各个点的最短路径,如果在寻找最短路径的过程中,搜到了搜过的点,说明出现负环。这两种方法,在判断负环上,深搜可能更快出结果。因此,对于n*m小于5000万的话,SPFA还是可以接受的,否则有可能超时,选深搜可能更好。

最后讲一下SPFA队列的大小:如果不出现负环,入队的点数一般不超过边数的10倍,一旦出现负环,入队的点数就是非常多的。因此,我们不能直接开一个大数组。我们可以用STL里面的队列,或者自己写一个循环队列。当然,你自认为运气好的话,可以直接开50倍边的队列,当入队次数超过50倍边,直接判断他出现负环。

程序实现

1、循环队列

2、使用STL队列

3、手动入队

4、深搜求最短路径

5、SPFA队列长度一般是边数量的10倍,超过太多的话,极有可能出现负环,但也有可能没有负环。

About

坚决不Copy代码!

本文标签:,,,,,

洛谷P1260工程规划:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!