负环 |
您所在的位置：网站首页 › spfa判负环运行时间长怎么办 › 负环 |
|
第一种：（不推荐） 统计每个点的入队次数，如果某一个点入队了n次，则说明存在负环。 第二种： 统计当前每个点的最短路的边数，如果存在负环，负环上的某一个点的最短路边数一定会是正无穷，只要边数超过n(节点数)，就可以判断存在负环。 特殊情况：图并不是全部连通，存在单独一个点没有入度和出度。这时候就不能只从某一个点进去找，有可能根本更新不到其他点。 这时候可以假设一个虚拟源点与所有的点都相连，并且距离为零。 一次把所有点入队，后续更新就可以检测出负环。 但以上这个方法被硬卡数据有可能超市，可以尝试 当所有点的入队次数超过2*n时，认为很大可能存在负环，但也可以被卡掉 传送门：判断负环 #include #include #include #include using namespace std; typedef pairPII; int n,m,idx; int h[100010],w[100010],e[100010],ne[100010]; int dist[100010],cnt[100010]; bool st[100010]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa() { queueq; q.push(1); for(int i=1;idist[t]+w[i]) { dist[j]=dist[t]+w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=n) return true; if(!st[j]) { q.push(j); st[j]=true; } } } } return false; } int main() { scanf("%d%d",&n,&m); memset(h,-1,sizeof h); while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } int t=spfa(); if(t) printf("Yes"); else printf("No"); return 0; } |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |