UVa 558 Wormholes

题目描述Wormholes\texttt{Wormholes}Wormholes题目要求判断给定的有向图中是否存在负权环。图中节点表示星系统边表示虫洞边权表示时间变化正数为未来负数为过去。若能通过某个环回到过去即总时间变化为负则可以无限回溯时间。需要判断是否存在这样的环。输入格式第一行一个整数ccc表示测试用例的数量。每个测试用例第一行包含两个整数nnn1≤n≤10001 \le n \le 10001≤n≤1000和mmm0≤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≤1000m≤2000m \le 2000m≤2000可接受。代码实现// Wormholes// UVa ID: 558// Verdict: Accepted// Submission Date: 2017-10-24// UVa Run Time: 0.030s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXV1100,MAXE100010,INF0x3f3f3f3f;structedge{intfrom,to,weight,next;}edges[MAXE];intn,m,head[MAXV];intdist[MAXV],parent[MAXV],visited[MAXV],counter[MAXV];boolspfa(intsource){for(inti0;in;i)dist[i]INF,parent[i]-1,visited[i]0,counter[i]0;dist[source]0,visited[source];queueintq;q.push(source);while(!q.empty()){intuq.front();q.pop();if(counter[u]n)returntrue;for(intihead[u];~i;iedges[i].next){intvedges[i].to,wedges[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;cincases;for(intc1;ccases;c){cinnm;memset(head,-1,sizeof(head));for(inti0;im;i){cinxyt;edges[i]edge{x,y,t,head[x]};head[x]i;}cout(spfa(0)?possible\n:not possible\n);}return0;}