虫洞【负环】模板题
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
农夫约翰在巡视他的众多农场时,发现了很多令人惊叹的虫洞。
虫洞非常奇特,它可以看作是一条 单向 路径,通过它可以使你回到过去的某个时刻(相对于你进入虫洞之前)。
农夫约翰的每个农场中包含 N 片田地,M 条路径(双向)以及 W 个虫洞。
现在农夫约翰希望能够从农场中的某片田地出发,经过一些路径和虫洞回到过去,并在他的出发时刻之前赶到他的出发地。
他希望能够看到出发之前的自己。
请你判断一下约翰能否做到这一点。
下面我们将给你提供约翰拥有的农场数量 F,以及每个农场的完整信息。
已知走过任何一条路径所花费的时间都不超过 1000010000 秒,任何虫洞将他带回的时间都不会超过 1000010000 秒。
输入格式
第一行包含整数 F,表示约翰共有 F 个农场。
对于每个农场,第一行包含三个整数 N,M,W。
接下来 M 行,每行包含三个整数 S,E,T,表示田地 S 和 E 之间存在一条路径,经过这条路径所花的时间为 T 。
再接下来 W 行,每行包含三个整数 S,E,T 表示存在一条从田地 S 走到田地 E 的虫洞,走过这条虫洞,可以回到 T 秒之前。
输出格式
输出共 F 行,每行输出一个结果。
如果约翰能够在出发时刻之前回到出发地,则输出 YES
,否则输出 NO
。
数据范围
1 ≤ F ≤ 5
1 ≤ N ≤ 500
1 ≤ M ≤ 2500
1 ≤ W ≤ 200
1 ≤ T ≤ 10000
1 ≤ S, E ≤ N
输入样例:
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
一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下,代码中的操作次数控制在 10 ^ 7 ∼ 10 ^ 8
为最佳。
n <= 100
-> O(n ^ 3)
-> 状态压缩dp
floyd
高斯消元
n <= 1000
-> O(n ^ 2)
O(n ^ 2 * log(n))
-> dp
,二分,朴素版Dijkstra、朴素版Prim、Bellman-Ford
n ≤ 100000
-> O(nlogn)
-> 各种sort,线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa
我的SPFA全题解
我的Dijkstra全题解
我的Bellman_fold全题解
我的Floyd全题解
我的Prim题解
我的Kruskal题解
解析
spfa
求负环直接看上面的链接,或者是我笔记里面的spfa
题解就有思路
这道题可见求回到过去的点,显然就是负环,找负环不需要初始化起点的距离,负环最起码需要负边,这样正边也不会进入队列,添加额外的计算负担,负边点才入队,负边点刷新次数大于 n - 1
,必有环。
import java.util.*;
import java.io.*;
public class Main {
static final int N = 510, M = 5410;
static int n, T, m, k, idx;
static int [] e = new int [M];
static int [] h = new int [N];
static int [] ne = new int [M];
static int [] w = new int [M];
static boolean [] st = new boolean [N];
static int [] cnt = new int [N];
static int [] d = new int [N];
static boolean spfa(){
Arrays.fill(d, 0);
Arrays.fill(st, false);
Arrays.fill(cnt, 0);
LinkedList <Integer> list = new LinkedList<>();
for (int i = 1; i <= n; i ++) {
list.add(i);
st[i] = true;
}
while(!list.isEmpty()){
int top = list.remove();
st[top] = false;
for (int i=h[top]; i != -1; i=ne[i]){
int j = e[i];
if (d[j] > d[top] + w[i]) {
d[j] = d[top] + w[i];
cnt[j] = cnt[top] + 1;
if (cnt[j] >= n) return true;
if (!st[j]){
st[j] = true;
list.add(j);
}
}
}
}
return false;
}
static void add(int a, int b, int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++;
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String [] args)throws IOException {
T = Integer.parseInt(br.readLine());
while (T -- > 0){
Arrays.fill(h, -1);
idx = 0;
String [] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
k = Integer.parseInt(s1[2]);
for (int i=0; i<m; i++){
String [] s2 = br.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
int c = Integer.parseInt(s2[2]);
add(a, b, c);
add(b, a, c);
}
for (int i=0; i<k; i++){
String [] s2 = br.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
int c = Integer.parseInt(s2[2]);
add(a, b, -c);
}
if (spfa()) System.out.println("YES");
else System.out.println("NO");
}
}
}