【SPFA判断负环】BZOJ1715- [Usaco2006 Dec]Wormholes 虫洞

【题目大意】

判断一张图中是否存在负环。

【思路】文章来源地址https://www.yii666.com/article/756143.html文章地址https://www.yii666.com/article/756143.html网址:yii666.com<网址:yii666.com文章来源地址:https://www.yii666.com/article/756143.html

dfs版SPFA。

 #include<bits/stdc++.h>
using namespace std;
struct edge
{
int to,len;
};
const int MAXN=+;
vector<edge> E[MAXN];
int f,n,m,w;
int vis[MAXN],dis[MAXN],flag; void addedge(int s,int e,int t)
{
E[s].push_back((edge){e,t});
} void init()
{
scanf("%d%d%d",&n,&m,&w);
for (int i=;i<MAXN;i++) vector<edge>().swap(E[i]);
for (int i=;i<=m;i++)
{
int s,e,t;
scanf("%d%d%d",&s,&e,&t);
addedge(s,e,t);
addedge(e,s,t);
}
for (int i=;i<=w;i++)
{
int s,e,t;
scanf("%d%d%d",&s,&e,&t);
addedge(s,e,-t);
}
} void spfa(int u)
{
if (vis[u])
{
flag=;
return;
}
vis[u]=;
for (int i=;i<E[u].size();i++)
{
int to=E[u][i].to,len=E[u][i].len;
if (dis[to]>dis[u]+len)
{
dis[to]=dis[u]+len;
spfa(to);
if (flag) return;
}
}
vis[u]=;
} void solve()
{
memset(vis,,sizeof(vis));
flag=;
for (int i=;i<=n;i++)
{
spfa(i);
if (flag) break;
}
puts(flag?"YES":"NO");
} int main()
{
scanf("%d",&f);
while (f--)
{
init();
solve();
} return ;
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png