一 原问题链接

Wormholes - POJ 3259 - Virtual Judge

https://vjudge.net/problem/POJ-3259

二 输入和输出

1 输入

第1行是单个整数 F，表示农场的数量。每个农场的第 1 行有3个整数N、M、W，表示编号为1~N块田，M 条路径和 W 个虫洞。第 2~M+1 行，每行都包含 3 个数字 S、E、T，表示穿过 S 与 E 之间的路径（双向）需要 T 秒。第 M+2~M+W+1 行，每行都包含 3 个数字 S、E、T，表示对从 S 到 E 的单向路径，旅行者将穿越 T 秒。

2 输出

对于每个农场，如果约翰可以达到目标，则输出“YES”，否则输出“NO”。

三 输入和输出样例

1 输入样例

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

 2 输出样例

NO

YES

四 分析

1 样例一分析

约翰无法在他出发之前的时间返回。

2 样例二分析

约翰可以在 1 > 2 > 3 > 1 的周期内及时返回，在他离开前1秒返回他的起始位置。他可以从周期内任何位置开始实行这一目标。因为存在一个负环（边权之和为负）1 > 2 > 3 > 1，边权之和为 -1。

五 算法设计

本问题其实就是判断是否有负环，使用 SPFA 判断负环即可。

注意：普通道路是双向的，虫洞是单向的，而且时间为负值。

六 代码

package graph.poj3259;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Poj3259 {
    static final int maxn = 505;
    static final int maxe = 100001;
    static final int inf = 0x3f3f3f3f;
    static int T;
    static int n;
    static int m;
    static int w;
    static int cnt;
    static node e[] = new node[maxe];
    static int head[] = new int[maxn];
    static int dis[] = new int[maxn];
    static int sum[] = new int[maxn];
    // 标记是否在队列中
    static boolean vis[] = new boolean[maxn];

    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new node();
        }
    }

    static void add(int u, int v, int c) {
        e[cnt].to = v;
        e[cnt].next = head[u];
        e[cnt].c = c;
        head[u] = cnt++;
    }

    static boolean spfa(int u) {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < vis.length; i++) {
            vis[i] = false;
        }
        // 统计入队的次数
        for (int i = 0; i < sum.length; i++) {
            sum[i] = 0;
        }
        vis[u] = true;
        dis[u] = 0;
        sum[u]++;
        q.add(u);
        while (!q.isEmpty()) {
            int x = q.peek();
            q.poll();
            vis[x] = false;
            for (int i = head[x]; i != -1; i = e[i].next) {
                if (dis[e[i].to] > dis[x] + e[i].c) {
                    dis[e[i].to] = dis[x] + e[i].c;
                    if (!vis[e[i].to]) {
                        if (++sum[e[i].to] >= n)
                            return false;
                        vis[e[i].to] = true;
                        q.add(e[i].to);
                    }
                }
            }
        }
        return true;
    }

    static boolean solve() {
        for (int i = 0; i < dis.length; i++) {
            dis[i] = inf;
        }
        for (int i = 1; i <= n; i++)
            if (dis[i] == inf) // 如果已经到达该点没找到负环，则不需要再从该点找
                if (!spfa(i))
                    return true;
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        T = scanner.nextInt();
        while (T-- > 0) {
            cnt = 0;
            n = scanner.nextInt();
            m = scanner.nextInt();
            w = scanner.nextInt();
            for (int i = 0; i < head.length; i++) {
                head[i] = -1;
            }

            int u, v, t;
            for (int i = 1; i <= m; i++) {
                u = scanner.nextInt();
                v = scanner.nextInt();
                t = scanner.nextInt();
                add(u, v, t); // 两条边
                add(v, u, t);
            }
            for (int i = 1; i <= w; i++) {
                u = scanner.nextInt();
                v = scanner.nextInt();
                t = scanner.nextInt();
                add(u, v, -t); // 一条边
            }
            if (solve())
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}

class node {
    int to;
    int c;
    int next;
}

七 测试