$$\mathrm{小K的农场}$$

题目链接：$\mathrm{l}\mathrm{u}\mathrm{o}\mathrm{g}\mathrm{u}\mathrm{P}1993$

题目

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

农场 $a$ 比农场 $b$ 至少多种植了 $c$ 个单位的作物；农场 $a$ 比农场 $b$ 至多多种植了 $c$ 个单位的作物；农场 $a$ 与农场 $b$ 种植的作物数一样多。

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

输入

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

接下来 $m$ 行：

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

输出

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

样例输入

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

样例输出

Yes

数据范围

对于 $100\%$ 的数据，保证 $1\le n,m,a,b,c\le 5\times 10^3$ 。

思路

这道题是差分约束。

其实就是一道差分约束的半模板题。

差分约束就是把一个一个约束条件变成一条边，然后如果这个图没有负环，就存在一种解，否则没有。

我们来化一下式子： $a-b\ge c$ $a-b\le c$ $a=b$ 可以变成： $b\le a-c$ $a\le b+c$ $a\le b+0$ 而且 $b\le a+0$

然后就按差分约束模板题来做就行了。

我近期应该会吧模板题做了，然后发链接上来。 模板题链接：https://blog.csdn.net/weixin_43346722/article/details/108935825

代码

#include<cstdio> #include<cstring> using namespace std; struct node { int x, to, next; }e[50001]; int n, m, a, b, c, d, le[50001], dis[50001], kk; bool in[50001]; void add(int x, int y, int z) { e[++kk] = (node){z, y, le[x]}; le[x] = kk; } bool spfa(int now) {//dfs的spfa最短路 in[now] = 1; for (int i = le[now]; i; i = e[i].next) if (e[i].x + dis[now] > dis[e[i].to]) { dis[e[i].to] = e[i].x + dis[now]; if (in[e[i].to] || !spfa(e[i].to)) return 0;//判断是否成了负环 } in[now] = 0; return 1; } int main() { memset(dis, -0x7f, sizeof(dis));//初始化 dis[0] = 0; scanf("%d %d", &n, &m);//读入 for (int i = 1; i <= m; i++) { scanf("%d %d %d", &a, &b, &c);//读入 if (a == 1) { scanf("%d", &d); add(c, b, d);//建图 } else if (a == 2) { scanf("%d", &d); add(b, c, -d);//建图 } else { add(c, b, 0);//建图 add(b, c, 0); } } for (int i = 1; i <= n; i++)//建图 add(0, i, 0); if (spfa(0)) printf("Yes");//能不能 else printf("No"); return 0; }