把三类作物数量关系统一成差分约束边，全点入队跑 SPFA 判负环，有负环即矛盾。
OJ: luogu
题目 ID: P1993
难度:普及+/提高-
标签:差分约束负环SPFApython
创建: 2026-07-17 03:00
更新: 2026-10-20 14:35
题意
判断「至少多
思路
把农场
三类信息的建边
| 题面写法 | 原始不等式 | 归一为 |
建边 |
|---|---|---|---|
1 a b c（ |
|||
2 a b c（ |
|||
3 a b（一样多） |
第二行最容易写反：
也可以用你顺手写出的三个等价式检查一遍：
判负环就是判矛盾
建好图后，把所有点距离取
- 队列能清空：说明不存在负环。此时每条边都满足
，所以最终距离本身就是一组满足全部约束的解，问题有解。 - 出现负环：沿环可以把一组变量无限改小却始终「满足」不等式，而实际数量不可能无限小，说明这些约束自相矛盾，输出
No。
负环的判定用路径边数：若某条更短的路走了至少
为什么不能单源
不同农场之间可能完全没有关系。如果只从
Python 知识
- 三类信息的参数个数不同（
c可有可无），用list(map(...))统一读成列表再按下标取，避免写三套split逻辑。 in_queue = bytearray(b"\x01") * (n + 1)一次把全部点标记为「在队列中」，正好对应全点入队这个初始状态，比先建列表再循环赋值紧凑。while queue and possible把「队列空」和「已发现负环」两个结束条件合在一个判断里，发现负环后不必清空队列。edge_count记录的是路径边数而不是入队次数，两者都能判负环，但路径边数的语义更直接：超过条边必然有环。
代码
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-17 01:40
# update_at: 2026-10-20 14:35
#
# main.py：小 K 的农场，差分约束的可行性问题——判断三类作物数量关系能否同时满足。
# 把每个农场看成变量 x_i，三类信息统一改写为 x_v <= x_u + w，建边 u -> v 权 w：
# type 1（a 比 b 至少多 c）：x_a - x_b >= c <=> x_b <= x_a - c，建边 a -> b 权 -c
# type 2（a 比 b 至多多 c）：x_a - x_b <= c <=> x_a <= x_b + c，建边 b -> a 权 c
# type 3（a 与 b 一样多）：x_a = x_b，即 a <= b 且 b <= a，建两个方向的 0 权边
# 所有点距离取 0 并全部入队（等价于 0 权超级源点）跑 SPFA；
# 没有负环说明约束可满足输出 Yes，出现负环说明自相矛盾输出 No。边权有负数，不能用 Dijkstra。
import sys
from collections import deque
input = sys.stdin.buffer.readline
n, constraints = map(int, input().split())
# graph[u]：若干 (终点 v, 边权 w)，代表 x_v <= x_u + w
graph = [[] for _ in range(n + 1)]
for _ in range(constraints):
operation = list(map(int, input().split()))
if operation[0] == 1:
# x_a - x_b >= c <=> x_b <= x_a - c
_, a, b, c = operation
graph[a].append((b, -c))
elif operation[0] == 2:
# x_a - x_b <= c <=> x_a <= x_b + c
_, a, b, c = operation
graph[b].append((a, c))
else:
# x_a == x_b，等价于 a <= b 且 b <= a，两个方向各一条 0 权边
_, a, b = operation
graph[a].append((b, 0))
graph[b].append((a, 0))
distance = [0] * (n + 1) # 当前差值上界，即一组候选解
edge_count = [0] * (n + 1) # 当前 distance 对应的路径边数，达到 n 说明绕出了负环
in_queue = bytearray(b"\x01") * (n + 1) # 全 1：所有点一开始都在队列里
queue = deque(range(1, n + 1))
possible = True
while queue and possible:
node = queue.popleft()
in_queue[node] = 0
for neighbor, weight in graph[node]:
candidate = distance[node] + weight
if candidate < distance[neighbor]:
distance[neighbor] = candidate
edge_count[neighbor] = edge_count[node] + 1
if edge_count[neighbor] >= n:
# 更短的路用了至少 n 条边，必然绕出了一个负环，即约束矛盾
possible = False
break
if not in_queue[neighbor]:
queue.append(neighbor)
in_queue[neighbor] = 1
print("Yes" if possible else "No")原有 C++ 版本仍保留：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-17 01:40
* update_at: 2026-10-20 14:35
*/
// 小 K 的农场：判断三类作物数量关系能否同时满足，是差分约束的可行性问题。
// 把每个农场看成变量 x_i，三类信息统一改写为 x_v <= x_u + w，建边 u -> v 权 w：
// type 1（a 比 b 至少多 c）：x_a - x_b >= c <=> x_b <= x_a - c，建边 a -> b 权 -c
// type 2（a 比 b 至多多 c）：x_a - x_b <= c <=> x_a <= x_b + c，建边 b -> a 权 c
// type 3（a 与 b 一样多）：x_a = x_b，建两个方向的 0 权边
// 所有点距离取 0 并全部入队（等价于加一个 0 权超级源点）跑 SPFA，
// 没有负环说明这组约束可以被满足，输出 Yes；出现负环说明约束自相矛盾，输出 No。
// 边权有负数，所以不能用 Dijkstra。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005; // 农场数上界 n <= 5e3
const int MAXM = 5005; // 信息数上界 m <= 5e3，每条信息最多加两条边
int n, m;
vector<pair<int, int>> graph[MAXN]; // graph[u]：若干 (终点 v, 边权 w)，代表 x_v <= x_u + w
long long dis[MAXN]; // 当前求出的差值上界，即一组候选解
int path_len[MAXN]; // 当前 dis 对应的路径边数，达到 n 说明绕出了环
bool in_queue[MAXN];
// 返回 false 表示存在负环、约束无解；返回 true 表示这组约束可以同时满足。
// 全局可行性检查：所有点初值取 0 并全部入队，等价于加一个到所有点都是 0 权边的超级源点。
// 初值只是假定值，解整体平移仍然合法，所以取 0 最省事。
bool feasible() {
fill(dis, dis + n + 1, 0);
fill(path_len, path_len + n + 1, 0);
fill(in_queue, in_queue + n + 1, true);
queue<int> que;
for (int u = 1; u <= n; u++) que.push(u);
while (!que.empty()) {
int u = que.front();
que.pop();
in_queue[u] = false;
for (const auto& e : graph[u]) {
int v = e.first;
long long w = e.second;
long long candidate = dis[u] + w;
if (candidate >= dis[v]) continue; // 这条边给不出更紧的上界
dis[v] = candidate;
path_len[v] = path_len[u] + 1;
if (path_len[v] >= n) return false; // 更短的路用了至少 n 条边，必然有负环
if (!in_queue[v]) {
que.push(v);
in_queue[v] = true;
}
}
}
return true;
}
void read_input() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int type;
cin >> type;
if (type == 1) {
int a, b, c;
cin >> a >> b >> c;
// x_a - x_b >= c <=> x_b <= x_a - c
graph[a].push_back({b, -c});
} else if (type == 2) {
int a, b, c;
cin >> a >> b >> c;
// x_a - x_b <= c <=> x_a <= x_b + c
graph[b].push_back({a, c});
} else {
int a, b;
cin >> a >> b;
// x_a == x_b，拆成两个方向的 0 权边
graph[a].push_back({b, 0});
graph[b].push_back({a, 0});
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
cout << (feasible() ? "Yes" : "No") << '\n';
return 0;
}复杂度
SPFA 最坏时间
对拍
gen.py 一半生成完全随机的信息（容易产生矛盾），一半先取一组真解再反推条件（保证可行），因此可解与不可解两种情形都会覆盖到；brute.cpp 直接枚举每个农场的作物数并检查三类信息是否全部成立，用来自动核对 main.cpp 与 main.py 的判定。
总结
文字里的「至少」「至多」「一样多」先移项成两个变量之差，再统一到同一个不等号方向，建边就不容易反。可行性问题只需判负环，不需要真的求出解。