传送门：【HDU】1317 XYZZY 题目分析：首先我们可以用spfa判最长路上是否有正权环，但是有正权环却不等价于能到达终点。这是我们还需要判断是否能从正权环中走到终点，这个可以用传递闭包搞定。如果没有正权环就看是否能从起点到终点就好了。 代码如下： #include <cstdio>#include <cstring>#include <algorithm>

UVA558 - Wormholes（BellmanFord判负环） UVA558 - Wormholes 题目大意：  有一个教授希望利用虫洞回到过去(还是从这个虫洞出来就到达了过去），给你虫洞形成的有向图，问教授能否回到过去。 解题思路:  利用BellmanFord判负环，如果不存在负环的话，那么最多经过N - 1次迭代就可以得到最短路，因为形成最短路最多N - 1个节点（起点不算

按照惯例，不想写题目大意，转一个 https://blog.csdn.net/liangzihao1/article/details/79716799 题目描述 Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows mu

题意：给出一个图，判断能不能从0出发，再回到0，经过边的权值为负。 判断图中有没有负环，并且负环上的点能回到0即可。 #include <bits/stdc++.h>using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1000 + 10;int dist[maxn];struct Edge{int u,

假如最终的答案是re。 那么对每条边进行一定的处理。 然后用spfa判断是否出现了负环。 如果出现了负环。说明所取的re偏小。 就这样二分re。 spfa判断负环的方法是如果某个点入队列超过n次，那么图中存在负环。 #include <iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<