负环

您所在的位置：网站首页 › spfa求负环 › 负环

负环

2023-08-01 07:27| 来源: 网络整理| 查看: 265

洛谷板子题

负环？是有负权边的环还是一个边权之和为负的环？

还没有准确的定义（那就先忽略吧qwq

判断负环的方法：

暴力枚举/spfa/mellman—ford/奇怪的贪心/超神的搜索

可惜我只会spfa

spfa：垂死病中惊坐起

有两种spfa可以用来求负环：dfs和bfs

在求负环上bfs要更好一些，dfs稍逊色一些

（注意：要memset，变量类型定义的时候要细致一些）

//bfs版spfa #include #include #include #include #define ll long long using namespace std; inline ll read() { ll sum = 0, p = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') p = -1; ch = getchar(); } while(ch >= '0' && ch dis[u] + e[i].wei) { dis[v] = dis[u] + e[i].wei; if(!vis[v]) { vis[v] = true; q.push(v); cnt[v] ++; if(cnt[v] >= n) return true; } } } } return false; } int main() { t = read(); while(t--) { n = read(),m = read(); tot = 0; memset(e,0,sizeof(e)); memset(dis,0,sizeof(dis)); memset(head,0,sizeof(head)); memset(vis,false,sizeof(vis)); memset(cnt,0,sizeof(cnt)); int a,b,c; for(int i = 1; i = 0) add(b,a,c); } if(spfa(1)) printf("YE5\n"); else printf("N0\n"); } return 0; }

//dfs版spfa #include #include #include using namespace std; inline int read() { int sum = 0, p = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') p = -1; ch = getchar(); } while(ch >= '0' && ch dis[x] +e[i].wei) { if(vis[v] || flag) { flag = true; break; } dis[v] = dis[x] +e[i].wei; spfa(v); } } vis[x] = false; } int main() { t = read(); while(t--) { cnt = 0; flag = 0; memset(head,0,sizeof(head)); memset(dis,0,sizeof(dis)); memset(e,0,sizeof(e)); memset(vis,false,sizeof(vis)); n = read(),m = read(); int a,b,c; for(int i = 1;i = 0) add(b,a,c); } for(int i = 1;i

【本文地址】

负环

负环

今日新闻

推荐新闻