小 K 的农场

题意

判断至少、至多、相等三类农场数量关系能否同时满足。

思路

全部改写为 x_v <= x_u+w：至少关系反向并取负权，至多关系按上界建边，相等建两条 0 边。所有点从 0 开始做最短路，出现负环即矛盾。

Python 知识

不同长度操作行用 list(map(...)) 统一解析。
deque 和 bytearray 是 SPFA 的常用组合。
输出只取决于是否检测到负环。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40import sys
from collections import deque


input = sys.stdin.buffer.readline
n, constraints = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(constraints):
    operation = list(map(int, input().split()))
    if operation[0] == 1:
        _, a, b, c = operation
        graph[a].append((b, -c))
    elif operation[0] == 2:
        _, a, b, c = operation
        graph[b].append((a, c))
    else:
        _, a, b = operation
        graph[a].append((b, 0))
        graph[b].append((a, 0))

distance = [0] * (n + 1)
edge_count = [0] * (n + 1)
in_queue = bytearray(b"\x01") * (n + 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:
                possible = False
                break
            if not in_queue[neighbor]:
                queue.append(neighbor)
                in_queue[neighbor] = 1
print("Yes" if possible else "No")

原有 C++ 版本仍保留：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
 * 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-07-17 01:40
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}

复杂度

SPFA 最坏 O(nm)，空间 O(n+m)。

总结

文字中的至少/至多先移项，统一为一个松弛方向后更不容易建反边。

目录

题意

思路

Python 知识

代码

复杂度

总结