题目描述：
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式：
第一行包含整数 n 和 m。
接下来 m行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式：
如果图中存在负权回路，则输出 Yes，否则输出 No。
判断有没有负环，其实我们这里用一个数组存放到达每个点的边数，然后判断它的边数是否是大于等于顶点边数的，如果成立，那么就必然存在环，反之则没有。（因为n个顶点没有环的话，边最多就是n - 1）
#include#include #include //需要用到队列，以及一个初始化函数：memset() using namespace std; const int N = 10010; int n,m; int e[N],h[N],ne[N],w[N],idx; //邻接表的存储，有兴趣的可以去了解一下，w数组存储权值 int dis[N],cnt[N]; //dis数组存储到达点的距离，cnt数组存储到达每个点的边数 bool st[N]; //st数组用来标记队列里面的元素，如果在队列里面就为true,反之则为false void add(int a,int b,int c)//邻接表的存储模板 { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx ++; } bool spfa()//这也是一个spfa的模板 { queue q;//声明一个队列 for(int i = 1; i <= n; i ++ ) { st[i] = true; q.push(i); //将每个元素都存入队列，并且标记 } while (q.size())//只要队列不为空，就继续执行 { int t = q.front();//取队头元素 q.pop();//记得出队 st[t] = false;//出队过后，该元素就不在队列之中了，记得取消标记 for(int i = h[t]; i != -1; i = ne[i] ) { int j = e[i]; if(dis[j] > dis[t] + w[i]) { dis[j] = dis[t] + w[i]; cnt[j] = cnt[t] + 1;//记得边数加1 if(cnt[j] >= n) return true; //如果边数大于等于n，则说明存在环，返回true即可（为什么返回这个，你看下面的输出 //判断条件就懂了） if(!st[j]) { st[j] = true; q.push(j); } } } } return false;//返回这个就说明不存在环 } int main() { scanf("%d%d",&n,&m); memset(h,-1,sizeof(h));//记得初始化h数组 while (m --) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); //存图 } if(spfa()) printf("Yesn");//返回true说明有环，输出Yes else printf("Non");//否则无环输出No return 0; }
