当前位置:首页 > 图论 > 最短路径 > 正文
计蒜客17294蒜头君当大厨
2447+

题目大意:上菜很讲究,有些菜在前d分钟要上,有些菜则要在d分钟后才能上,还有些才要在某些菜上了之和才能上,最早什么时候上完n份菜?

蒜头君苦练厨艺,终于成为了某高档酒店的大厨。

每天上班,蒜头君会被要求做 份菜。既然是高档酒店,那么客人们当然是很讲究的,尤其对于上菜的时间有很多要求。客人们的要求被分成下列四种:

  1. 菜品 的上菜时间必须比菜品 的上菜时间早 分钟或者更早。
  2. 菜品 的上菜时间必须比菜品 的上菜时间迟 分钟或者更迟。
  3. 菜品 的上菜时间在 分钟以后(包含 分钟)。
  4. 菜品 的上菜时间在 分钟之前(包含 分钟)。

蒜头君的上班时间记为 分钟。为了节约时间,在满足客人们要求的情况下,蒜头君希望最后上的一道菜的时间尽可能的早。(每道菜的上菜时间必须不早于蒜头君的上班时间

输入格式

第一行输入一个整数 ,表示一共需要上 道菜。

第二行输入一个整数 ,表示客人们的要求数量。

接下里 行,每行先输入一个整数

  • 如果 ,表示描述里的第 种要求,后面跟着三个整数
  • 如果 ,表示描述里的第 种要求,后面跟着三个整数
  • 如果 ,表示描述里的第 种要求,后面跟着两个整数
  • 如果 ,表示描述里的第 种要求,后面跟着两个整数

输出格式

如果蒜头君能满足客人们的要求,输出最后一道菜的上菜时间;否则输出一行 I can't

数据范围和约定

对于 的数据:

对于 的数据:,并且输入保证有解。

对于 的数据:

样例解释 1

的上菜时间分别为 ,这样能满足输入客人们的所有要求,并且时间最短。

样例解释 2

,合并以后得到 ,不可能满足客人们的所有要求。

样例输入1

3
5
2 3 2 10
2 2 1 2
2 3 2 5
1 2 3 7
3 3 9

样例输出1

12

样例输入2

3
4
3 1 3
2 3 1 9
2 1 3 -1
1 1 2 5

样例输出2

I can't

样例输入3

17
20
2 6 3 -21
1 8 2 54
3 7 -95
4 11 44
1 5 15 40
3 9 1
3 3 30
3 8 23
2 9 12 -15
4 13 61
2 3 7 31
1 5 10 -15
2 16 1 43
2 12 3 -79
2 14 16 -51
3 6 48
4 7 0
2 10 11 -59
2 12 17 -29
3 4 10

样例输出3

77

解题思路

第3、4条限制条件,分别指一道菜的最早上菜时间和最晚上菜时间,不难想到拓扑排序。a比b早c,则建立一条a指向b权值为c的有向边;a比b晚c,也就是b比a早c,即建立一条b指向a权值为c的有向边。建图后,拓扑排序,如果出现环就不可行?不是的!数据中有负数,虽然搞不清楚负数分钟的实际意义是什么,当出现了负数,就可以出现环了,只有不是正环就行。比如1比2早9,2比1早-10,这是有解的,0时刻上菜1,9时刻上菜2,这样两个条件都满足。

遇到可以出现环的“拓扑排序”怎么办?用差分约束系统,a比b早c,也就是b>=a+c,这样可以建立一条a指向b权值为c的有向边。其他条件也转化成大于等于的约束条件,这样我们就可以通过求最长路来满足所有约束条件。当然,你要全部转成小于等于再求最短路也行。(如果出现入队次数非常多,多到会超时,基本上就是出现正环/负环,即无解)

求最短路/最长路为什么能解决差分约束系统问题?以最长路为例,在求解过程中,如果出现不满足约束条件的情况,那么结点的路程就会更新、更大,继续影响其他点,直到不能再进行“松弛”操作,也就是所有条件都满足了。与普通SPFA相比,不同的是不是从某个起点开始,而且所有点都入队求解,这样才能让每个点都满足约束条件。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

计蒜客17294蒜头君当大厨:等您坐沙发呢!

发表评论

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