文档介绍：查分约束系统
T1-工程规划-work
【问题描述】 造一幢大楼是一项艰巨的工程,它是由 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个任务,都可以在瞬间做完
我们做这n个任务的时刻分别为T1,T2,T3,T4…
我们对这n个任务的时刻有m组要求
我们假设每组要求的格式为Ti,Tj,b
我们的要求是Ti-Tj<=b
样例1
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
样例2
5 5  1 2 -3  1 5 -1  2 5 -1  5 1 -5  4 1 4
NO SOLUTION
不等式
x-y<=1
x-y<=1
x<=y+1
y-x>=-1
注意,后一个在数学上貌似是不对的
让我们推倒一下
Ti-Tj<=b
Ti<=Tj+b
观察一下有没有想到什么?
dist[i]<=dist[j]+v[j][i]
这是一个目标状态
如何达到目标状态呢?
如果dist[i]>dist[j]+v[j][i]
那么dist[i]=dist[j]+v[j][i]
最终就可以达到前面的状态。
查分约束系统的思想
既然我们可以把一个形如Ti-Tj<=b的不等式转化为Ti<=Tj+b的目标状态
那么我们就可以建图,由点j向点i连一条长度为b的单向边
然后以某一个点为起点,定义它的值位0。
求出最短路,即为答案。
当然此题需要处理一下使他们都大于零
最长路最短路
当然也不只是求最短路,也可以求最长路
最长路和最短路的区别在于约束条件的转化不同
那么请你自己推一下最长路的约束条件应该是怎么样的
也就是推一下那个目标状态
练****题 P1227 关系运算图
描述 Description 给出一有向图,图中每条边都被标上了关系运算符‘<’,‘>’,‘=’。现在要给图中每个顶点标上一个大于等于0,小于等于k的某个整数使所有边上的符号得到满足。若存在这样的k,则求最小的k,若任何k都无法满足则输出NO。 例如下表中最小的k为2。 结点1>结点2 结点2>结点3 结点2>结点4 结点3=结点4 如果存在这样的k,输出最小的k值;否则输出‘NO’。