当前位置:首页 > 差分约束 > 正文
洛谷P1993小K的农场
2696+

题目大意:有n个农场,已知m个农场之间的作物多少关系,请问这些关系是否有冲突?

题目描述

小 K 在 Minecraft 里面建立很多很多的农场,总共 n 个,以至于他自己都忘记了每个农场中种植作物的具体数量了,他只记得一些含糊的信息(共 m 个),以下列三种形式描述:

  1. 农场 a 比农场 b 至少多种植了 c 个单位的作物。
  2. 农场 a 比农场 b 至多多种植了 c 个单位的作物。
  3. 农场 a 与农场 b 种植的作物数一样多。

但是,由于小 K 的记忆有些偏差,所以他想要知道存不存在一种情况,使得农场的种植作物数量与他记忆中的所有信息吻合。

输入输出格式

输入格式:

第一行包括两个整数 n 和 m,分别表示农场数目和小 K 记忆中的信息数目。

接下来 m 行:

如果每行的第一个数是 1,接下来有 3 个整数 a,b,c,表示农场 a 比农场 b 至少多种植了 c 个单位的作物。

如果每行的第一个数是 2,接下来有 3 个整数 a,b,c,表示农场 a 比农场 b 至多多种植了 c 个单位的作物。

如果每行的第一个数是 3,家下来有 2 个整数 a,b,表示农场 a 终止的数量和 b 一样多。

输出格式:

如果存在某种情况与小 K 的记忆吻合,输出“Yes”,否则输出“No”。

输入输出样例

输入样例#1:

3 3
3 1 2
1 1 3 1
2 2 3 2

输出样例#1:

Yes

说明

对于 100% 的数据保证:1 ≤ n,m,a,b,c ≤ 10000。

解题思路

一样多即a>=b&&b>=a;a比b至少多c即a>=b+c;a比b至多多c即a<=b+c。将所有表达式转成小于等于后求最短路,a<=b+c即b到a有一条c的边,a越小就“越满足条件”,如果有解即不会出现负环就Yes。当然,全部转成>=求最长路也是可以的,a>=b+c即b到a有一条c的边,a越大就“越满足条件”,只要没有正环就有解。

判断是否出现负环、正环,用深度比较快——搜索过程中,如果更新了搜索中的点,那么会重头再更新一圈,一直下去,因此,如果发现更新的点是访问中的就说明有环无解!

使用SPFA找环,一般是判断一个点入队超过n次就有环,但一个点入队n次,那么边也要访问n次那么多,很容易超时。SPFA一般是很快的,如果出现慢的情况,很可能就是有环,因为我们如果发现平均每个点入队很多次,超过了正常的速度,再做下去很可能超时,此时就很可能有环了。宁可答案错误,也不要超时,break输出NO吧!

为什么不能用拓扑排序?

首先可以有环,只是不允许有正环或者负环,有环就无法找到入度为0的点;如果求最长路,不能有正环,求最短路,不能有负环。假设是求最长路,那么把所有边转成正的,判断有无环不就行了吗?还是不行,因为边的含有不一样了:大于等于求最长路、小于等于求最短路。如a比b至多多1,c比b至少多1,a比c至少多1,他是无解的,但转成正边却无环。

程序实现

深搜判环,速度比SPFA快:

SPFA入队n次,竟然会超时。

About

坚决不Copy代码!

本文标签:,,,,,,

洛谷P1993小K的农场:等您坐沙发呢!

发表评论

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