题目描述
Wormholes\texttt{Wormholes}Wormholes题目要求判断给定的有向图中是否存在负权环。图中节点表示星系统，边表示虫洞，边权表示时间变化（正数为未来，负数为过去）。若能通过某个环回到过去（即总时间变化为负），则可以无限回溯时间。需要判断是否存在这样的环。
输入格式
第一行一个整数ccc，表示测试用例的数量。每个测试用例第一行包含两个整数nnn（1≤n≤10001 \le n \le 10001≤n≤1000）和mmm（0≤m≤20000 \le m \le 20000≤m≤2000）。接下来mmm行，每行三个整数xxx、yyy、ttt（−1000≤t≤1000-1000 \le t \le 1000−1000≤t≤1000），表示从xxx到yyy的虫洞，时间变化为ttt。
输出格式
对于每个测试用例，输出一行possible或not possible。
样例
输入
2 3 3 0 1 1000 1 2 15 2 1 -42 4 4 0 1 10 1 2 20 2 3 30 3 0 -60输出
possible not possible题目分析
本题的核心是检测有向图中是否存在负权环。可以使用Bellman-Ford\texttt{Bellman-Ford}Bellman-Ford或SPFA\texttt{SPFA}SPFA算法。
算法
- 从源点000开始运行SPFA\texttt{SPFA}SPFA。
- 若某个节点入队次数超过nnn，则存在负权环。
复杂度分析
SPFA\texttt{SPFA}SPFA最坏O(n×m)O(n \times m)O(n×m)，n≤1000n \le 1000n≤1000，m≤2000m \le 2000m≤2000，可接受。
代码实现
// Wormholes// UVa ID: 558// Verdict: Accepted// Submission Date: 2017-10-24// UVa Run Time: 0.030s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXV=1100,MAXE=100010,INF=0x3f3f3f3f;structedge{intfrom,to,weight,next;}edges[MAXE];intn,m,head[MAXV];intdist[MAXV],parent[MAXV],visited[MAXV],counter[MAXV];boolspfa(intsource){for(inti=0;i<n;i++)dist[i]=INF,parent[i]=-1,visited[i]=0,counter[i]=0;dist[source]=0,visited[source]++;queue<int>q;q.push(source);while(!q.empty()){intu=q.front();q.pop();if(counter[u]>n)returntrue;for(inti=head[u];~i;i=edges[i].next){intv=edges[i].to,w=edges[i].weight;if(dist[v]>dist[u]+w){dist[v]=dist[u]+w,parent[v]=u;if(!visited[v])q.push(v),visited[v]++,counter[v]++;}}visited[u]--;}returnfalse;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases,x,y,t;cin>>cases;for(intc=1;c<=cases;c++){cin>>n>>m;memset(head,-1,sizeof(head));for(inti=0;i<m;i++){cin>>x>>y>>t;edges[i]=edge{x,y,t,head[x]};head[x]=i;}cout<<(spfa(0)?"possible\n":"not possible\n");}return0;}
