查分约束系统-王毅峰课件

查分约束系统T1-工程规划-work【问题描述】

造一幢大楼是一项艰巨的工程，它是由n个子任务构成的，给它们分别编号1，2，…，n(5≤n≤1000)。由于对一些任务的起始条件有着严格的限制，所以每个任务的起始时间T1，T2，…，Tn并不是很容易确定的(但这些起始时间都是非负整数，因为它们必须在整个工程开始后启动)。例如：挖掘完成后，紧接着就要打地基；但是混凝土浇筑完成后，却要等待一段时间再去掉模板。这种要求就可以用M(5≤m≤5000)个不等式表示，不等式形如Ti一Tj≤b代表i和j的起始时间必须满足的条件。每个不等式的右边都是一个常数b，这些常数可能不相同，但是它们都在区间(-l00，100)内。你的任务就是写一个程序，给定像上面那样的不等式，找出一种可能的起始时间序列T1，T2，…，Tn，或者判断问题无解。对于有解的情况，要使最早进行的那个任务和整个工程的起始时间相同，也就是说，T1，T2，…，Tn中至少有一个为0。题目大意我们有n个任务，都可以在瞬间做完我们做这n个任务的时刻分别为T1,T2,T3,T4…我们对这n个任务的时刻有m组要求我们假设每组要求的格式为Ti,Tj,b我们的要求是Ti-Tj<=b样例255

12-3

15-1

25-1

51-5

414NOSOLUTION不等式x-y<=1x-y<=1x<=y+1y-x>=-1注意，后一个在数学上貌似是不对的让我们推倒一下Ti-Tj<=bTi<=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’。对于a<b，他和之前我们的Ti-Tj<=b的区别有两个，一个是常数项，另一个是不能相等。因为是整数，所以可以进行转化a+1<=b然后再推倒一下建图就可以了然后建立一个源点，从源向其他所有点连一条权值为0的单向边以源点为出发点，进行一遍最短路什么时候无解？存在负权回路的就是无解。还有一道作业题P1624layoutFj的牛每天要排队去吃饭。

现在有N(2<=N<=1000)只牛要排队吃饭，这个队伍我们可以认为是数轴，数轴上每个整数点我们认为可以站牛，并且可以站无数头牛。

牛们对排队的顺序有要求，如果有两头牛的关系很好，他们之间的距离不能超过一定的距离，如果有两头牛关系不好，他们的距离不能低于一定的距离。

在满足这个所有条件的基础上，