终于开始认真对待图论了
因为听说一直是提高组的，动得很少，直到现在机房打提高的氛围下，开始学一些皮毛的东西
模板题目链接
这是一道求负环的题目，照理来说大家都是用spfa来判断负环的
但是我觉得bellman-ford更优
并且在这个模板题目中，spfa开O2过，bellman不开O2还比spfa快？
为什么呢？
因为
关于spfa
——他死了
（所以机房基本所有人转dijistra了）
但是dijistra无法解决负环问题
因此选择bellman和spfa（队列优化的bellman）
其实还可以用其他方法过掉，比如
SPFA他死了算法
思路
因为出现负环的时候会一直循环循环循环……
然后TLE
所以在原版spfa上加一个cnt数组记录一个点出队的次数
如果出队次数大于点数，就说明一定出现负环了
因此加给判断就可以了
题外话
之前xzjds给我讲了邻接表储存，但是后来发现其实广泛叫做链式前向星而不是叫做邻接表……
如果不会的话可以百度
要储存边的话还可以用向量容器和玄学结构体（将会在bellman里使用）
代码
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define memset0(a) memset(a,0,sizeof a)
#define memset1(a) memset(a,127,sizeof a)
#define N 500005
using namespace std;
int tot,m,n,s;
int ne[N], la[N], link[N], co[N], dis[N];
int cnt[N];
//important
bool vis[N];
inline int read() {
int f =
1, x =
0;
char ch;
do { ch = getchar();
if (ch ==
'-')f = -
1; }
while (ch<
'0' || ch>
'9');
do { x = x *
10 + ch -
'0'; ch = getchar(); }
while (ch >=
'0'&&ch <=
'9');
return f *
x;
}
void add(
int x,
int y,
int z)
{
tot++; ne[tot] = y; co[tot] = z; la[tot] = link[x]; link[x] =
tot;
}
bool spfa(
int s)
{
memset1(dis);
memset0(vis);
memset0(cnt);
queue<
int>
q;
q.push(s);
vis[s] =
true;
dis[s] =
0;
while (!
q.empty())
{
int now =
q.front();
q.pop();
vis[now] =
false;
//?
if (cnt[now] >= n)
return true;
for (
int k = link[now]; k; k =
la[k])
{
if (dis[ne[k]] > dis[now] +
co[k])
{
dis[ne[k]] = dis[now] +
co[k];
if (vis[ne[k]] ==
false)
{
q.push(ne[k]);
vis[ne[k]] =
true;
cnt[ne[k]]++
;
if (cnt[ne[k]] >= n)
return true;
}
}
}
}
return false;
}
int main()
{
int T=
read();
while (T--
)
{
memset0(link);
n = read(), m =
read();
s =
1; tot =
0;
; for (
int i =
1; i <= m; i++
)
{
int x=read(), y=read(), z=
read();
add(x, y, z);
if (z >=
0) add(y, x, z);
}
if(spfa(s))puts(
"YE5");
else puts(
"N0");
}
return 0;
}
spfa
是的，不加O2会TLE。只有90分。
由于本蒟蒻不会优化，因此学习了更好的bellman判断负环
Bellman-ford算法
思路
可以把dis数组一开始都设为0
先全部松弛操作一遍（relaxing一遍）
然后再去松弛，如果能松弛，就是有负环
这个相对spfa来说，当数据点数小的时候，时间是比spfa快的
当然如果RP不好spfa速度会更快
为什么每次都有题外话
用的边的储存方式是从大佬@Planet6174 看来的
感觉非常玄学但是很容易使用
代码
#include<bits/stdc++.h>
#define N 500005
using namespace std;
int tot,m,n,s;
int dis[N];
inline int read() {
int f =
1, x =
0;
char ch;
do { ch = getchar();
if (ch ==
'-')f = -
1; }
while (ch<
'0' || ch>
'9');
do { x = x *
10 + ch -
'0'; ch = getchar(); }
while (ch >=
'0'&&ch <=
'9');
return f *
x;
}
struct eg{
int u,v,w;
eg(int u =
0,
int v =
0,
int w =
0) : u(u), v(v), w(w) {}
} edge[N];
bool bellman_ford()
{
memset(dis,0,
sizeof(dis));
for(
int i=
1;i<=n-
1;i++
)
for(
int j=
1;j<=m;j++
)
if (dis[edge[j].u] + edge[j].w <
dis[edge[j].v])
dis[edge[j].v] = dis[edge[j].u] +
edge[j].w;
for (
int j =
1; j <= m; j++
)
if (dis[edge[j].u] + edge[j].w <
dis[edge[j].v])
return true;
return false;
}
int main()
{
int T=
read();
while (T--
)
{
n = read(), m =
read();
; for (
int i =
1; i <= m; i++
)
{
edge[i].u=read(), edge[i].v=read(), edge[i].w=
read();
edge[i].u--; edge[i].v--
;
if (edge[i].w >=
0) {
++i; ++m; edge[i] = eg(edge[i -
1].v, edge[i -
1].u, edge[i -
1].w);
}
}
if(bellman_ford()) puts(
"YE5");
else puts(
"N0");
}
return 0;
}
bellman-ford
就是这样了
转载于:https://www.cnblogs.com/lincold/p/9860875.html
