把三种记忆化成 x_v≤x_u+w 的差分约束边,加超级源点后用 SPFA 判负环:无负环则输出 Yes,有负环则输出 No。
OJ: roj
题目 ID: 1724
难度:普及+/提高-
标签:图论差分约束最短路SPFApython
创建: 2026-10-07 18:46
更新: 2026-10-07 18:46
形式化题目
给定
1 a b c:(农场 至少比 多 ); 2 a b c:(农场 至多比 多 ); 3 a b:。
判断是否存在一组赋值同时满足全部约束,满足输出 Yes,否则输出 No。
约束中
正解
思路
三类约束都是变量差值的限制,这正是差分约束系统的标准形状:把每条约束改写成
:连边 ,权 ; :连边 ,权 ; :双向各连一条权 的边。
化完之后,“存在一组赋值满足全部约束”
图可能不连通,因此加超级源点 No;跑完未发现负环输出 Yes。
本题只问可行性、不问具体赋值,且所有约束只限制差值(解可整体平移), 所以不需要关心作物数量是否非负——可行性判据与平移无关。
代码
#!/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-10-07 18:40
# update_at: 2026-10-07 18:40
import sys
from collections import deque
from collections.abc import Iterator
INF = 10**18 # 最短路初值哨兵,远大于任何约束路径和(c ≤ 1e4,边数 ≤ 3e4)
type Edge = tuple[int, int, int] # (起点, 终点, 边权):一条化好的约束边
def build_edges(data: Iterator[int], m: int) -> list[Edge]:
"""把 m 条记忆逐条化成差分约束的边 x_v <= x_u + w。"""
edges: list[Edge] = []
for _ in range(m):
op = next(data)
a, b = next(data), next(data)
if op == 1: # a 至少比 b 多 c:x_b <= x_a - c
c = next(data)
edges.append((a, b, -c))
elif op == 2: # a 至多比 b 多 c:x_a <= x_b + c
c = next(data)
edges.append((b, a, c))
else: # a 与 b 一样多:双向各一条 0 权边
edges.append((a, b, 0))
edges.append((b, a, 0))
return edges
def has_negative_cycle(edges: list[Edge], n: int) -> bool:
"""SPFA 从超级源点判负环:某点入队次数超过点数(含源点)即存在负环。"""
# 超级源点 0 连向每个农场(权 0):图不连通也能一次判完整
edges = edges + [(0, i, 0) for i in range(1, n + 1)]
adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)] # 邻接表 adj[u] = [(v, w)]
for u, v, w in edges:
adj[u].append((v, w))
dist = [INF] * (n + 1)
enq_cnt = [0] * (n + 1) # 累计入队次数,Bellman-Ford 队列法的负环判据
in_queue = [False] * (n + 1)
dist[0] = 0
queue = deque([0])
in_queue[0] = True
enq_cnt[0] = 1
total_nodes = n + 1 # 农场 1..n 再加超级源点 0
while queue:
u = queue.popleft()
in_queue[u] = False
for v, w in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if not in_queue[v]:
enq_cnt[v] += 1
if enq_cnt[v] > total_nodes:
return True
queue.append(v)
in_queue[v] = True
return False
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
edges = build_edges(data, m)
print("No" if has_negative_cycle(edges, n) else "Yes")
if __name__ == "__main__":
solve()/**
* 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-10-07 18:40
* update_at: 2026-10-07 18:40
*/
// 1724《小K的农场》:差分约束系统判可行解。
// 三种记忆分别化成 x_v <= x_u + w 的边,加超级源点后用 SPFA 判负环:
// 有负环 <=> 约束互相矛盾(无解);无负环 <=> 存在一种赋值吻合所有记忆。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10005; // n <= 1e4,再留 1 个编号给超级源点 0
const int MAXE = 40005; // 3 型约束双向共 2m 条边 + 源点 n 条边 <= 3e4
// 链式前向星:to/w/nxt 是同一条边的三个字段(边编号即下标)
int head[MAXN], to[MAXE], nxt[MAXE];
ll w[MAXE]; // 边权,约束里的 c 可达 1e4,松弛路径累加用 ll 更稳妥
int edge_cnt;
// 加一条 u -> v、边权为 weight 的有向边
void add_edge(int u, int v, ll weight) {
edge_cnt++;
to[edge_cnt] = v;
w[edge_cnt] = weight;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
ll dist[MAXN]; // dist[u] 表示超级源点到 u 的最短路估计(松弛上界)
int enq_cnt[MAXN]; // 某点入队累计次数,超过点数即判定负环
bool in_queue[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
for (int i = 0; i < m; i++) {
int op, a, b;
cin >> op >> a >> b;
if (op == 1) {
// 农场 a 至少比 b 多 c:x_a - x_b >= c <=> x_b <= x_a - c
ll c;
cin >> c;
add_edge(a, b, -c);
} else if (op == 2) {
// 农场 a 至多比 b 多 c:x_a - x_b <= c <=> x_a <= x_b + c
ll c;
cin >> c;
add_edge(b, a, c);
} else {
// 农场 a 与 b 一样多:双向各一条 0 权边
add_edge(a, b, 0);
add_edge(b, a, 0);
}
}
// 超级源点 0 连向所有农场(权 0):图不连通也能一次判完整
for (int i = 1; i <= n; i++) add_edge(0, i, 0);
memset(dist, 0x3f, sizeof(dist));
dist[0] = 0;
queue<int> q;
q.push(0);
in_queue[0] = true;
enq_cnt[0] = 1;
int total_nodes = n + 1; // 含超级源点
while (!q.empty()) {
int u = q.front();
q.pop();
in_queue[u] = false;
for (int e = head[u]; e != 0; e = nxt[e]) {
int v = to[e];
if (dist[u] + w[e] < dist[v]) {
dist[v] = dist[u] + w[e];
if (!in_queue[v]) {
in_queue[v] = true;
enq_cnt[v]++;
// Bellman-Ford 队列法标准判据:某点入队次数超过点数 => 负环
if (enq_cnt[v] > total_nodes) {
cout << "No\n";
return 0;
}
q.push(v);
}
}
}
}
cout << "Yes\n";
return 0;
}两份代码是同一算法:先按三种记忆建边,再加超级源点,SPFA 判负环。
C++ 版用静态链式前向星存图,Python 版用邻接表 + deque,均为标准库实现。
复杂度
- 时间:SPFA 均摊接近
( 为点松弛轮数),边数 , 实测 10 个数据点均为毫秒级;最坏退化情形 ,本题规模下不会触发。 - 空间:
,两个版本实测峰值内存均在 10 MB 以内。
总结
差分约束的套路是固定的:约束改写成
数据与验证说明(如实记录)
- 素材源
std.cpp已在真实数据data/的 10 个点上全部实跑,与.out完全一致, 故作为算法参考使用;本题解的两份代码为独立改写,未照抄。 - 样例(1 组):
main.cpp与main.py实际输出均为Yes,与期望一致。 - 真实数据:
main.cpp经check_sample.py验证 10/10 PASS;main.py用同样.in逐点运行并与.out比对,10/10 一致。 - 本题素材源附带
data.py生成脚本(cyaron 分层造数据),说明data/为自造测试 数据;题面与一本通 1724 / 洛谷 P1993 逐字一致,但本仓验证结论仅对随仓数据成立, 不等同于官方 OJ 的 AC 判定。