「一本通 3.3 练习 2」虫洞

题目描述

给定 $F$ 个农场，每个农场有 $N$ 块地、 $M$ 条无向正权小路（耗时 $T$ 秒）和 $W$ 个有向虫洞（可回到 $T$ 秒前）。判断能否从某块地出发、绕一圈后回到出发时刻之前：能输出 YES，否则输出 NO。每个农场先读 $N,M,W$ ，再依次读 $M$ 行小路和 $W$ 行虫洞；数据范围 $1\le F\le5$ ， $1\le N\le500$ ， $1\le M\le2500$ ， $1\le W\le200$ ， $|T|\le10^4$ 。样例：输入为 2、3 3 1、1 2 2、1 3 4、2 3 1、3 1 3、3 2 1、1 2 3、2 3 4、3 1 8（每项一行），对应输出 NO 和 YES。

思路

“回到出发时刻之前”等价于存在总权为负的闭环，而负闭环必含负环，故只需判定负环。建图时小路无向、权为 $T$ ，虫洞有向、权取 $-T$ ；把所有点的初始距离设为 $0$ （相当于加超级源点，覆盖不连通分量），做 $n$ 轮全量松弛：第 $n$ 轮仍能松弛即存在负环输出 YES，某轮无松弛就提前退出输出 NO。单农场复杂度 $O(n(2m+w))$ 。

参考代码

Python 版：

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
40
41
42
43
44
45
46#!/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-09-30 15:06
# update_at: 2026-09-30 15:06

import sys


def has_negative_cycle(n: int, edges: list[tuple[int, int, int]]) -> bool:
    """图里是否存在负环：以超级源点做 n 轮松弛，第 n 轮还能松弛即有负环。

    "回到出发时刻之前"等价于存在总权为负的闭环（闭环必含负环），
    所以只判负环，不必关心起点和具体路径。
    """
    dist = [0] * (n + 1)  # 超级源点到各点初值都为 0：一轮同时覆盖所有连通块
    for _ in range(n):
        relaxed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                relaxed = True
        if not relaxed:  # 本轮无松弛：距离已稳定，之后不可能再松弛
            return False
    return True  # 第 n 轮仍在松弛 → 存在负环


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    F = next(data)

    for _ in range(F):
        n, m, w = next(data), next(data), next(data)  # 农场规模：地/小路/虫洞
        # 小路无向：来回各记一条正权边；虫洞有向：时间倒流，权取负。
        roads = [(next(data), next(data), next(data)) for _ in range(m)]
        edges = roads + [(e, s, t) for s, e, t in roads]  # 反向边，读入顺序不变
        edges += [(next(data), next(data), -next(data)) for _ in range(w)]
        out.append('YES' if has_negative_cycle(n, edges) else 'NO')

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * 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-06 00:26
 * update_at: 2026-10-06 00:26
 */

#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXN = 505;
const int MAXE = 5205;

int n, m, w;    // 一个农场的规模：地、小路、虫洞
int edge_cnt;   // 当前农场已记录的边数
int eu[MAXE];   // eu[i] 表示第 i 条边的起点
int ev[MAXE];   // ev[i] 表示第 i 条边的终点
ll ew[MAXE];    // ew[i] 表示第 i 条边的权（虫洞取负）
ll dist[MAXN];  // dist[i] 表示超级源点到第 i 块地的最短时间

// 加一条 u -> v、权为 weight 的有向边。
void add_edge(int u, int v, ll weight) {
    edge_cnt++;
    eu[edge_cnt] = u;
    ev[edge_cnt] = v;
    ew[edge_cnt] = weight;
}

// 判断当前农场是否存在负环：以超级源点做 n 轮松弛，第 n 轮仍能松弛即有负环。
// "回到出发时刻之前"等价于存在总权为负的闭环，而负闭环必含负环，故只需判负环。
bool has_negative_cycle() {
    for (int i = 1; i <= n; i++)
        dist[i] = 0; // 超级源点到各点初值都为 0，一轮即可覆盖所有连通块
    for (int round = 1; round <= n; round++) {
        bool relaxed = false;
        for (int i = 1; i <= edge_cnt; i++) {
            if (dist[eu[i]] + ew[i] < dist[ev[i]]) {
                dist[ev[i]] = dist[eu[i]] + ew[i];
                relaxed = true;
            }
        }
        if (!relaxed)
            return false; // 本轮无松弛：距离已稳定，之后不可能再变小
    }
    return true; // 第 n 轮仍在松弛，存在负环
}

void solve() {
    int F;
    scanf("%d", &F);
    for (int farm = 1; farm <= F; farm++) {
        scanf("%d %d %d", &n, &m, &w);
        edge_cnt = 0;
        // 小路无向且权为正：来回各记一条边。
        for (int i = 1; i <= m; i++) {
            int s, e;
            ll t;
            scanf("%d %d %lld", &s, &e, &t);
            add_edge(s, e, t);
            add_edge(e, s, t);
        }
        // 虫洞有向且时间倒流：只记一条权为 -t 的边。
        for (int i = 1; i <= w; i++) {
            int s, e;
            ll t;
            scanf("%d %d %lld", &s, &e, &t);
            add_edge(s, e, -t);
        }
        if (has_negative_cycle())
            printf("YES\n");
        else
            printf("NO\n");
    }
}

int main() {
    solve();
    return 0;
}