锐客网

  1. 首页 > it技术 > >

洛谷 P2850 [USACO06DEC]虫洞Wormholes

题目描述 While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.
As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .
To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.
John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N （从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。 现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。
输入输出格式 输入格式：
Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.
输出格式：
Lines 1..F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).
输入输出样例 输入样例#1：

2 3 3 1 1 2 2 1 3 4 2 3 1 3 1 3 3 2 1 1 2 3 2 3 4 3 1 8

输出样例#1：
NO YES

说明 For farm 1, FJ cannot travel back in time.
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.


题目的大意应该已经很清楚了。
不过在此之前我也没做过负环的题，然后就按着最短路的思路写了一下。
【洛谷 P2850 [USACO06DEC]虫洞Wormholes】最初我是直接跑一遍BFS版的SPFA，然后记录下遍历过的点。
如果某个点遍历过2次，那么就有环，否则无环。
然后一遍过了样例就直接交上去了。然后不加优化果然是T了的。


然后某位dalao告诉我负环可以用DFS版的SPFA。
其实两个版本的SPFA都差不多。
思路和注释差不多都在代码里了 其实是我好像没什么好讲的了233。


#include #include #include #include using namespace std; const int MAXN=10001; int k,n,m,w,tot=0; int Head[MAXN],Dis[MAXN]; //Head表示邻接表的头点，Dis[i]表示从起始点到i点的当前距离。 bool visit[MAXN],flag=0; //visit记录是否遍历到了这个点。 struct edge//邻接表存图 { int next,node,w; }h[MAXN*4]; void add(int u,int v,int w)//加点 { h[++tot].next=Head[u]; h[tot].node=v; h[tot].w=w; Head[u]=tot; //虽然有重边但是不用去判断了。 } void SPFA(int x) { if(flag) return ; visit[x]=1; //记录下所有遍历的点 for(int i=Head[x]; i; i=h[i].next)//和跑最短路基本一样 { if(flag) return ; int v=h[i].node; if(Dis[v]>Dis[x]+h[i].w) { Dis[v]=Dis[x]+h[i].w; if(visit[v])//如果已经遍历过了就直接跳出去了。 { flag=1; return ; } else SPFA(v); //继续遍历 } } visit[x]=0; //回溯的时候将遍历过的点还原 } int main() { cin>>k; while(k--) { tot=0; //每个数据要记得清0, flag=0; memset(h,0,sizeof(h)); memset(visit,0,sizeof(visit)); memset(Head,0,sizeof(Head)); memset(Dis,0,sizeof(Dis)); //这里需要注意一下，Dis初始设置成0能跳过很多路径， cin>>n>>m>>w; //直接找到负数点所在的环。 for(int i=1; i<=m; i++) { int x,y,z; cin>>x>>y>>z; add(x,y,z); add(y,x,z); //正权边是双向的需要注意一下。 } for(int i=1; i<=w; i++) { int x,y,z; cin>>x>>y>>z; add(x,y,-z); //这道题很方便的就是负权边都放一起了不用去打判断。 } for(int i=1; i<=n; i++) //其实吧，这里随便找个点SPFA都行，毕竟有负环从哪个点开始都能找到， {//而且只要跑一遍就行了。 if(flag) break; //发现负环直接退出循环。 SPFA(i); } if(flag) cout<<"YES"<


    推荐阅读


    上一篇：ACM/计算机基础算法|【白话算法】如何根据动态规划数组求得最佳策略

    下一篇：开宗明义|最具独创精神的数学家——黎曼