小K的农场

GitHub跳转原题关系图返回列表

把三种记忆化成 x_v≤x_u+w 的差分约束边,加超级源点后用 SPFA 判负环:无负环则输出 Yes,有负环则输出 No。

OJ: roj

题目 ID: 1724

难度:普及+/提高-

标签:图论差分约束最短路SPFApython

创建: 2026-10-07 18:46

更新: 2026-10-07 18:46

形式化题目

给定 nn 个变量 x1,…,xnx_1,\dots,x_n 与 mm 条约束,约束有三种形式:

  • 1 a b c:xa−xb⩾cx_a - x_b \geqslant c(农场 aa 至少比 bb 多 cc);
  • 2 a b c:xa−xb⩽cx_a - x_b \leqslant c(农场 aa 至多比 bb 多 cc);
  • 3 a b:xa=xbx_a = x_b。

判断是否存在一组赋值同时满足全部约束,满足输出 Yes,否则输出 No。 约束中 1⩽n,m,a,b,c⩽100001 \leqslant n, m, a, b, c \leqslant 10000。

正解

思路

三类约束都是变量差值的限制,这正是差分约束系统的标准形状:把每条约束改写成 xv⩽xu+wx_v \leqslant x_u + w 的形式,再在图上连一条 u→vu \to v 权 ww 的有向边。逐条化边:

  1. xa−xb⩾c  ⟺  xb⩽xa+(−c)x_a - x_b \geqslant c \iff x_b \leqslant x_a + (-c):连边 a→ba \to b,权 −c-c;
  2. xa−xb⩽c  ⟺  xa⩽xb+cx_a - x_b \leqslant c \iff x_a \leqslant x_b + c:连边 b→ab \to a,权 cc;
  3. xa=xbx_a = x_b:双向各连一条权 00 的边。

化完之后,“存在一组赋值满足全部约束”   ⟺  \iff 图中没有负环。直觉是:若存在负环 u1→u2→⋯→uk→u1u_1 \to u_2 \to \cdots \to u_k \to u_1,沿环把所有不等式相加得到 0⩽(负数)0 \leqslant (\text{负数}), 矛盾;反之无负环时,以超级源点为起点跑单源最短路,令 xi=dist(i)x_i = \mathrm{dist}(i), 每条边的松弛不等式 dist(v)⩽dist(u)+w\mathrm{dist}(v) \leqslant \mathrm{dist}(u) + w 恰好就是原约束,即得到一组可行解。

图可能不连通,因此加超级源点 00,向每个农场连一条权 00 的边,从 00 一次 SPFA 即可判完整张图。判据用 Bellman-Ford 队列法的标准写法:统计每个点的入队次数, 某点入队次数超过点数(含源点,即 n+1n+1)即存在负环,输出 No;跑完未发现负环输出 Yes。

本题只问可行性、不问具体赋值,且所有约束只限制差值(解可整体平移), 所以不需要关心作物数量是否非负——可行性判据与平移无关。

代码

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-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()
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-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 均摊接近 O(km)O(km)(kk 为点松弛轮数),边数 2m+n⩽3×1042m + n \leqslant 3\times 10^4, 实测 10 个数据点均为毫秒级;最坏退化情形 O(nm)O(nm),本题规模下不会触发。
  • 空间:O(n+m)O(n + m),两个版本实测峰值内存均在 10 MB 以内。

总结

差分约束的套路是固定的:约束改写成 xv⩽xu+wx_v \leqslant x_u + w → 建边 → 加超级源点 → SPFA/Bellman-Ford 判负环。关键在于把"至少多 cc"翻译成 −c-c 权的边方向, 以及记住"可行   ⟺  \iff 无负环"这一判据;只问可行性时无需还原具体赋值。


数据与验证说明(如实记录)

  • 素材源 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 判定。