东莞网站的制作设计,网站开发设计总结,深圳正规网站建设公司,wordpress 导航调用代码文章目录 负环spfa找负环方法一方法二实际效果 负环 环内路径上的权值和为负。
spfa找负环
两种基本的方法
统计每一个点的入队次数#xff0c;如果一个点入队了n次#xff0c;则说明存在负环统计当前每个点中的最短路中所包含的边数#xff0c;如果当前某个点的最短路所… 文章目录 负环spfa找负环方法一方法二实际效果 负环 环内路径上的权值和为负。
spfa找负环
两种基本的方法
统计每一个点的入队次数如果一个点入队了n次则说明存在负环统计当前每个点中的最短路中所包含的边数如果当前某个点的最短路所包含的边数大于等于n也说明存在负环
实际上两种方法是等价的都是判断是否路径包含n条边 n n n条边的话就有 n 1 n1 n1个点 用的更多的还是第二种方法。
方法一 c n t [ x ] : 表示 x 的入队次数 cnt[x]:表示x的入队次数 cnt[x]:表示x的入队次数
#include bits/stdc.h
#define int long long
#define rep(i,a,b) for(int i (a); i (b); i)
#define fep(i,a,b) for(int i (a); i (b); --i)
#define pii pairint, int
#define ll long long
#define db double
#define endl \n
#define x first
#define y second
#define pb push_back
#define inf 0x3f3f3f3f*1llusing namespace std;void solve()
{int n,m1,m2;cinnm1m2;vectorvectorpiig(n1);rep(i,1,m1){int u,v,w;cinuvw;g[u].pb({v,w});g[v].pb({u,w});} rep(i,1,m2){int u,v,w;cinuvw;g[u].pb({v,-w});}vectorintinq(n1,0);vectorintcnt(n1,0);vectorintd(n1,0);queueintq;rep(i,1,n){q.push(i);inq[i]1;}while(q.size()){auto tq.front();q.pop();int ut;inq[u]0;for(auto it:g[u]){int vit.x,wit.y;if(d[v]d[u]w){d[v]d[u]w;if(!inq[v]){q.push(v);inq[v]1;cnt[v];if(cnt[v]n){coutYESendl;return;}}}}}coutNOendl;
}signed main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen(1.in, r, stdin);int _;cin_;while(_--)solve();return 0;
}方法二 c n t [ x ] : 表示从起点到 x 所经过的最短路径的边数 cnt[x]:表示从起点到x所经过的最短路径的边数 cnt[x]:表示从起点到x所经过的最短路径的边数
#include bits/stdc.h
#define int long long
#define rep(i,a,b) for(int i (a); i (b); i)
#define fep(i,a,b) for(int i (a); i (b); --i)
#define pii pairint, int
#define ll long long
#define db double
#define endl \n
#define x first
#define y second
#define pb push_back
#define inf 0x3f3f3f3f*1llusing namespace std;void solve()
{int n,m1,m2;cinnm1m2;vectorvectorpiig(n1);rep(i,1,m1){int u,v,w;cinuvw;g[u].pb({v,w});g[v].pb({u,w});} rep(i,1,m2){int u,v,w;cinuvw;g[u].pb({v,-w});}vectorintinq(n1,0);vectorintcnt(n1,0);vectorintd(n1,0);queueintq;rep(i,1,n){q.push(i);inq[i]1;}while(q.size()){auto tq.front();q.pop();int ut;inq[u]0;for(auto it:g[u]){int vit.x,wit.y;if(d[v]d[u]w){d[v]d[u]w;cnt[v]cnt[u]1;if(cnt[v]n){coutYESendl;return;}if(!inq[v]){q.push(v);inq[v]1;}}}}coutNOendl;
}signed main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen(1.in, r, stdin);int _;cin_;while(_--)solve();return 0;
}
实际效果 方法一跑出来的结果是 1024 m s 1024ms 1024ms 方法二跑出来的结果是 671 m s 671ms 671ms
