水题笔记_ 负环 [图论, dfs-spfa, 最短路, 负环]

我宽嫂就是没思路 爆零 被FST 也不会刷你们洛谷一点水题

真香

懵逼的 题目

传送至 某谷

扯淡的 题解

判断负环…一般用到的方法主要就是SPFA…SPFA有两样写法,你知道么

  1. BFS-SPFA: 直接记录每一个节点入队的次数, 如果cnt[b[i].to]大于n就可以直接退出了, 然而期望是$\mathrm O(nm)$的, 这个丧心病狂的题就别想了…
  2. DFS-SPFA: 只记录dis和当前节点是否在本次DFS中被访问过, 有点类似于tarjan(都是dfs), 只不过要求的是负环…

你以为这样就结束了?

恭喜, 你已经有了20分了…

优化

  1. 如果b[i].to在本次DFS中被访问过了, 不必判断dis是否为负(?) 因为如果绕了一圈又回到这个点, 而dis变小了, 说明绕的这一圈总边权一定为负(?)
  2. 初始化dis的时候不必初始化为0x7f直接初始化为0即可, 因为是找负环(?)

感觉上面的优化都挺不靠谱的…但是反正Luogu的数据能过…

沙茶的 代码

我很想知道最优解那些人是怎么卡的….

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#define MAXN (200000 + 5)
#define MAXM (200000 + 5)
#define INF (0x7ffffff)
using namespace std;
struct edg
{
int from, to, next, cost;
}b[MAXM << 1];
int g[MAXN], cntb, ans, dis[MAXN];
bool vis[MAXN];
char pans[2][5] = {"N0", "YE5"};
int n, m;
void adn(int from, int to, int cost)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
b[cntb].cost = cost;
g[from] = cntb;
}
void spfa(int);
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
memset(dis, 0, sizeof(dis));
memset(vis, false, sizeof(vis));
memset(g, 0, sizeof(g));
cntb = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int srx, sry, srz;
scanf("%d%d%d", &srx, &sry, &srz);
adn(srx, sry, srz);
if (srz > 0)
adn(sry, srx, srz);
}
ans = 0;
for (int i = 1; i <= n; i++)
if (!vis[i])
{
dis[i] = 0, spfa(i);
if (ans) break;
}
printf("%s\n", pans[ans]);
}
return 0;
}
void spfa(int dq)
{
vis[dq] = true;
for (int i = g[dq]; i; i = b[i].next)
{
if (dis[b[i].to] > dis[dq] + b[i].cost)
{
dis[b[i].to] = dis[dq] + b[i].cost;
if (vis[b[i].to])
{
ans = 1;
return ;
}
else
spfa(b[i].to);
if (ans)
return ;
}
}
vis[dq] = false;
}

/*
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
*/

By 失去梦想的 Cansult