终于开始认真对待图论了
因为听说一直是提高组的，动得很少，直到现在机房打提高的氛围下，开始学一些皮毛的东西
这是一道求负环的题目，照理来说大家都是用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; }
是的，不加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; }
就是这样了