利用SPFA判负环。如果一个节点出队N次有负环这里记录一下
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} int cnt[1010]; bool inq[1010]; int d[1010]; int w[1010][1010],N,M; vector<int>G[1010]; queue<int>q; bool SPFA() { memset(cnt,0,sizeof(cnt)); memset(inq,false,sizeof(inq)); memset(d,0x3f,sizeof(d)); while (!q.empty()) q.pop(); q.push(0); cnt[0]++; inq[0] = true; d[0] = 0; while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = 0; i < (int)G[u].size(); i++) { int v = G[u][i]; if (d[v] > d[u] + w[u][v]) { d[v] = d[u] + w[u][v]; if (!inq[v]) { inq[v] = true; cnt[v]++; if (cnt[v] >= N) return true; q.push(v); } } } } return false; } int main() { //freopen("sample.txt","r",stdin); int T; scanf("%d",&T); while (T--) { scanf("%d%d",&N,&M); for (int i = 0; i < 1010; i++) G[i].clear(); while (M--) { int u,v,we; scanf("%d%d%d",&u,&v,&we); G[u].push_back(v); w[u][v] = we; } if (SPFA()) puts("possible"); else puts("not possible"); } return 0; }