题目描述
判断路径是否存在负环
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你判断图中是否存在负权回路。
算法
思路:抽屉原理,若n个点中,从某个点开始到达n的路径边数大于n,则存在负环
存储:邻接表
具体代码
import java.util.*;
import java.io.*;
public class Main {
private static int INF = 0x3f3f3f3f;
private static int N = 100010;
private static int idx = 0;
private static int[] e = new int[N];
private static int[] ne = new int[N];
private static int[] h = new int[N];
private static boolean[] st = new boolean[N]; // 标记是否访问
private static int[] w = new int[N]; // 权重
private static int[] dist = new int[N]; // 路径权重
private static int[] cnt = new int[N]; // 记录经过的边数
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] line = reader.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int m = Integer.parseInt(line[1]);
Arrays.fill(h, -1);
// Arrays.fill(dist, INF);
for (int i=0; i<m; i++) {
line = reader.readLine().split(" ");
int a = Integer.parseInt(line[0]);
int b = Integer.parseInt(line[1]);
int c = Integer.parseInt(line[2]);
add(a, b, c);
}
if (spfa(n)) System.out.println("Yes");
else System.out.println("No");
}
private static boolean spfa(int n) {
Queue<Integer> q = new LinkedList<>();
for (int i=1; i<=n; i++) {
q.offer(i);
st[i] = true;
}
while (!q.isEmpty()) {
int t = q.poll();
st[t] = false;
for (int i=h[t]; i!=-1; i=ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) { // 重量记在开始端
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j]) {
q.offer(j);
st[j] = true;
}
}
}
}
return false;
}
private static void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c; // 重量记在开始端
ne[idx] = h[a];
h[a] = idx++;
}
}