Problem Solving►UVa

UVa 558 - Wormholes

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

看是否能無止盡的回到過去，也就是有負環的存在。

Solution

利用 SPFA 或 Bellman-Ford 判斷負環即可。

Code

SPFA

UVa 558UVa 558(1) - Wormholes
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
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#define N 1000
#define MAX 100000000
using namespace std;

struct Node{

    int b, t;
    Node(){}
    Node(int v, int w) : b(v), t(w){}
};
vector<Node> edge[N];
bool SPFA(int n);
int main()
{
    int Case, n, m;
    scanf("%d", &Case);
    while (Case--)
    {
        int a, b, t, i;
        scanf("%d%d", &n, &m);
        for (i = 0; i < n; i++)
            edge[i].clear();
        for (i = 0; i < m; i++)
        {
            scanf("%d%d%d", &a, &b, &t);
            edge[a].push_back(Node(b, t));
        }

        puts(SPFA(n) ? "possible" : "not possible");
    }

    return 0;
}
bool SPFA(int n)
{
    bool in[N] = {};
    int d[N];
    fill(d, d + n, MAX);
    d[0] = 0;

    int r[N] = {};//³Ìµu¸ô®|ªºÃä¼Æ
    queue<int> Q;
    Q.push(0);

    while (!Q.empty())
    {
        int next = Q.front();
        Q.pop();

        in[next] = false;
        for (Node node : edge[next])
        {
            if (d[next] + node.t < d[node.b])
            {
                d[node.b] = d[next] + node.t;
                r[node.b] = r[next] + 1;
                if (r[node.b] > n - 1)
                    return true;
                if (!in[node.b])
                {
                    Q.push(node.b);
                    in[node.b] = true;
                }
            }
        }

    }

    return false;
}

Bellman-Ford

UVa 558UVa 558(2) - Wormholes
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
#include<cstdio>
#include<algorithm>
#define N 2001
#define MAX 100000000
using namespace std;

int a[N], b[N], t[N];
bool BellmanFord(int n, int m);
int main()
{
    int Case, n, m;
    scanf("%d", &Case);
    while (Case--)
    {
        int i;
        scanf("%d%d", &n, &m);
        for (i = 0; i < m; i++)
            scanf("%d%d%d", &a[i], &b[i], &t[i]);
        puts(BellmanFord(n, m) ? "possible" : "not possible");
    }

    return 0;
}
bool BellmanFord(int n, int m)
{
    int d[N];
    fill(d, d + n, MAX);
    d[0] = 0;

    //bellman ford
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < m; j++)
            if (d[a[j]] != MAX)
                if (d[a[j]] + t[j] < d[b[j]])
                    d[b[j]] = d[a[j]] + t[j];

    //negative cycle check
    for (int j = 0; j < m; j++)
        if (d[a[j]] + t[j] < d[b[j]])
            return true;

    return false;
}