[USACO06DEC]Wormholes G
题目背景
题目描述
John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边,并可以使你返回到过去的一个时刻(相对你进入虫洞之前)。
John 的每个农场有
现在 John 希望能够从某块地出发,走过一条路径回到出发点,且同时也回到了出发时刻以前的某一时刻。请你告诉他能否做到。
输入格式
输入的第一行是一个整数
每组测试数据的格式如下:
每组数据的第一行是三个用空格隔开的整数,分别代表农田的个数
每组数据的第
每组数据的第
输出格式
对于每组测试数据,输出一行一个字符串,如果能回到出发时刻之前,则输出 YES
,否则输出 NO
。
样例 #1
样例输入 #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
提示
样例 2 解释
John 只需要沿着
数据范围与约定
对于
分析
这道题目存在着两种道路,一种是连接双向边的花费为正的道路,另一种是连接单向边花费为负的虫洞,题目要求我们找到一个花费为负的道路。其实就是一个裸的SPFA判断负环的题。这里介绍一下DFS版本SPFA判断负环。
DFS版的SPFA应用可能就只有判负环了,它判断负环的时间复杂度为
而DFS版本的SFPA更加简单,它只需要看现在更新答案的节点之前有没有访问过,如果已经访问过,那么一定存在负环。
CODE
#include <iostream> #include <algorithm> using namespace std; const int maxn = 8000; struct node { int next, to, data; } edge[maxn]; int head[maxn], n, m, w, cnt = 0; inline void add_edge(int from, int to, int data) { edge[++cnt] = (node){head[from], to, data}; head[from] = cnt; } int vis[maxn] = {}, dis[maxn]; bool dfs(int x) // SPFA { if (vis[x]) return true; vis[x] = true; for (register int i = head[x]; i; i = edge[i].next) { if (dis[edge[i].to] > dis[x] + edge[i].data) { dis[edge[i].to] = dis[x] + edge[i].data; if (dfs(edge[i].to)) return true; } } vis[x] = false; return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t --> 0) { cnt = 0; cin >> n >> m >> w; for (register int i = 0; i < maxn; i++) // 多测清空 { head[i] = 0; edge[i] = (node){0, 0, 0}; vis[i] = 0; dis[i] = 2147483647; } for (register int i = 1, u, v, p; i <= m; i++) { cin >> u >> v >> p; add_edge(u, v, p); add_edge(v, u, p); } for (register int i = 1, u, v, p; i <= w; i++) { cin >> u >> v >> p; add_edge(u, v, -p); } for (register int i = 1; i <= n; i++) // 设立超级原点 add_edge(n + 1, i, 0); dis[n + 1] = 0; if (dfs(n + 1)) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
Comments NOTHING