P3385 【模板】负环
题目描述
给定一个 n 个点的有向图，请求出图中是否存在从顶点 1 出发能到达的负环。
负环的定义是：一条边权之和为负数的回路。
输入格式
输入的第一行是一个整数 T，表示测试数据的组数。对于每组数据的格式如下：
第一行有两个整数，分别表示图的点数 n 和接下来给出边信息的条数 m。
接下来 m 行，每行三个整数 u, v, w。
- 若 w≥0，则表示存在一条从 u 至 v 边权为 w 的边，还存在一条从 v 至 u 边权为 w 的边。
- 若 w < 0，则只表示存在一条从 u 至 v 边权为 w 的边。
输出格式
对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO。
输入输出样例
输入
2 3 4 1 2 2 1 3 4 2 3 1 3 1 -3 3 3 1 2 3 2 3 4 3 1 -8
输出
NO YES
怎么判断负环呢
使用spfa跑一遍最短路,然后用一个数组cnt记录每个点的入队次数,入队次数大于了n,就是有负环,跑了一遍没找到,就没有
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node{
int to,dis;
};
int T;
vector<node>a[N];
int dis[N];
int vis[N];
int cnt[N];
int n,m;
queue<int>q;
bool spfa(){
for(int i=1;i<=n;i++)dis[i]=2147483647;
dis[1]=0;
q.push(1);
vis[1]=1;
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=0;
for(int i=0;i<a[x].size();i++){
int v=a[x][i].to;
int w=a[x][i].dis;
if(dis[v]>dis[x]+w){
dis[v]=dis[x]+w;
if(vis[v]==0){
vis[v]=1;
q.push(v);
cnt[v]++;
}
if(cnt[v]>n)return true;
}
}
}
return false;
}
signed main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(vis));
while(!q.empty())q.pop();
for(int i=1;i<=n;i++)a[i].clear();
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
a[u].push_back(node{v,w});
if(w>=0)a[v].push_back(node{u,w});
}
if(spfa())printf("YES\n");
else printf("NO\n");
}
}原文地址：https://blog.csdn.net/STY_fish_2012/article/details/138028553
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！