題目： UVa - 558 - Wormholes

題目說明

給一張有權重的向圖，求圖上是否有負環。

Input： 第一行為一整數，表示有幾組測資，每組測資第一行為兩個整數 n、m，表示有 n 個點及 m 條邊，後面 m 行，每行有三個整數 u、v、w，表示有 u -> v 的邊且權重為 w。

Output： 若圖上有負環則輸出 "possible"，否則輸出 "not possible"。

解題思路

這個解法需要有 Bellman Ford 演算法的概念。

先讀取測資並建圖，之後先執行 Bellman Ford，之後再遍歷所有邊，若任意點還能再更短則表示有負環。

參考解法

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

struct edge
{
    int u;
    int v;
    int w;
};

// data
vector<edge> edges;
int dist[1000];

void init(int n)
{
    edges.clear();
    fill(dist, dist + n, INT_MAX);
}

// 如果有負環則回傳 true
bool bellman(int n)
{
    // 從 0 開始
    dist[0] = 0;

    // 若不存在負環，則做 n - 1 次後 dist 會儲存 0 到每個點的最短路徑
    for (int i = 0; i < n - 1; ++i) for (auto& [u, v, w] : edges)
        if (dist[u] != INT_MAX) dist[v] = min(dist[u] + w, dist[v]);

    // 若任意點還能再更短則表示有負環
    for (auto& [u, v, w] : edges) if (dist[v] > dist[u] + w) return true;

    return false;
}

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        int n, m;
        cin >> n >> m;
        init(n);

        // 建圖
        while (m--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            edges.push_back({ u, v, w });
        }

        if (bellman(n)) cout << "possible\n";
        else cout << "not possible\n";
    }
}