spfa判断负环(转载)_crystal spfa求负环

判断给定的有向图中是否存在负环。

利用 spfa算法判断负环有两种方法:

1)spfa 的 dfs形式,判断条件是存在一点在一条路径上出现多次。

2)spfa 的 bfs形式,判断条件是存在一点入队次数大于总顶点数。

代码如下:

法 1 (spfa的 dfs形式):

#include<iostream>

#include<cstdio>

#include<cstring>

usingnamespace std;

const intoo = 1 << 30;

const intmaxn = 1010;

structEdge {

int u, v, t, next;

}edge[2010];

intprev[maxn], p[maxn], d[maxn];

boolvis[maxn], flag;

inttot;

voidaddEdge(int u, int v, int t) {

edge[tot].u = u;

edge[tot].v = v;

edge[tot].t = t;

edge[tot].next = prev[u];

prev[u] = tot ++;

}

voidspfa(int u) {

int v;

for (int i = prev[u]; i != -1; i = edge[i].next) {

v = edge[i].v;

if (d[u] + edge[i].t < d[v]) {

if (vis[v]) {//存在一点在一条路径上出现多次

flag = true;

return ;

}

else {

d[v] = d[u] + edge[i].t;

vis[v] = true;

spfa(v);

}

}

}

}

int main(){

//freopen("input.txt", "r", stdin);

//freopen("output.txt", "w", stdout);

int T;

int a, b, t;

int n, m;

scanf("%d", &T);

while (T --) {

scanf("%d%d", &n, &m);

memset(prev, -1, sizeof(prev));

tot = 0;

for (int i = 1; i <= m; i ++) {

scanf("%d%d%d", &a, &b,&t);

addEdge(a, b, t);

}

memset(vis, false, sizeof(vis));

fill(d, d + n, oo);

d[0] = 0;

flag = false;

spfa(0);

if (flag) printf("possiblen");

else printf("not possiblen");

}

return 0;

}

法 2 (spfa的 bfs形式):

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

usingnamespace std;

const intoo = 1 << 30;

const intmaxn = 1010;

structEdge {

int u, v, t, next;

}edge[2010];

intprev[maxn], p[maxn], d[maxn], in[maxn];

boolvis[maxn];

inttot;

queue<int> q;

voidaddEdge(int u, int v, int t) {

edge[tot].u = u;

edge[tot].v = v;

edge[tot].t = t;

edge[tot].next = prev[u];

prev[u] = tot ++;

}

boolspfa(int n) {

int u, v;

while (!q.empty()) q.pop();

memset(vis, false, sizeof(vis));

memset(in, 0, sizeof(in));

fill(d, d + n, oo);

d[0] = 0; vis[0] = true;

q.push(0);

while (!q.empty()) {

u = q.front();

vis[u] = false;

for (int i = prev[u]; i != -1; i = edge[i].next) {

v = edge[i].v;

if (d[u] + edge[i].t < d[v]) {

d[v] = d[u] + edge[i].t;

if (!vis[v]) {

in[v] ++;

if (in[v] > n) return true;//存在一点入队次数大于总顶点数

vis[v] = true;

q.push(v);

}

}

}

spfa判断负环(转载)_crystal spfa求负环

vis[u] = false;

q.pop();

}

return false;

}

int main(){

//freopen("input.txt", "r", stdin);

//freopen("output.txt", "w", stdout);

int T;

int a, b, t;

int n, m;

scanf("%d", &T);

while (T --) {

scanf("%d%d", &n, &m);

memset(prev, -1, sizeof(prev));

tot = 0;

for (int i = 1; i <= m; i ++) {

scanf("%d%d%d", &a, &b,&t);

addEdge(a, b, t);

}

if (spfa(n)) printf("possiblen");

else printf("not possiblen");

}

return 0;

}

  

爱华网本文地址 » http://www.413yy.cn/a/25101010/19190.html

更多阅读

转载 奇门求财法二 奇门求财术

不错原文地址:奇门求财法(二)作者:杨鸿利时空风水◎奇门求财法-11:如果你的钱财怎么都留不住,想要旺财聚财者,可在家中财位摆放一尊貔貅神兽、三脚金蟾蜍或是聚宝盆,也可在墙面挂上招财童子或刘海戏金蟾的图画,以求偏财旺运及长聚财源。◎奇

SPFA算法 弗洛伊德算法

介绍:单源最短路径的算法最常用的是Dijkstra,些算法从时间复杂度来说为O(n^2),但是面对含有负权植的图来说就无能为力了,此时Dellman-ford算法就有用了,这咱算法是采用的是动态规化的思想,但是1994年西南交通大学段凡丁发表了SPFA(Shorte

新常态 机关党建 思考 中国啤酒行业新常态格局下的营销思考

2014年1-12月份,中国啤酒行业累计产量4921.85吨,同比下降0.96。这是中国啤酒行业二十多年来的首次负增长!   这种负增长很容易让人联想到一个当下的经济热词:新常态!啤酒行业的新常态是个什么样子呢?   1、 行业增速放缓。行业从两

声明:《spfa判断负环(转载)_crystal spfa求负环》为网友闲云池中敛分享!如侵犯到您的合法权益请联系我们删除