POJ 3259 Wormholes ( SPFA判断负环 && 思维 )
2024-10-07 11:33:44
题意 : 给出 N 个点,以及 M 条双向路,每一条路的权值代表你在这条路上到达终点需要那么时间,接下来给出 W 个虫洞,虫洞给出的形式为 A B C 代表能将你从 A 送到 B 点,并且回到 C 个时间点之前,也就是时光倒流了 C 个时间并且此时你在 B 点,现在问你是否能够在图上的这些点中走,使得在某一个点刚好碰到之前的自己
分析 : 冷静分析一下,只要是有负权回路的某一条边属于虫洞的,那么肯定是能在这个环上一直绕,直到遇到之前的自己,如果将虫洞看作一条负权边的话,那么问题就变成了只要存在负环,那么肯定是能够通过负环回路达到见到过去的自己这种操作的,用SPFA判一下就OK了!最好自己好好分析一下,为什么只要环上有虫洞就能达到目的,这个证明是很重要的!
#include <iostream> #include <cstdio> #include <cmath> #include <queue> #include <string.h> using namespace std; const int INF=0x3f3f3f3f; ; struct EdgeNode{ int v, w, nxt; }; EdgeNode Edge[maxn*maxn]; bool vis[maxn]; int Head[maxn], Dis[maxn], cnt; int N, M; int PushCnt[maxn]; ///记录每一个节点的入队次数、方便判断负环 inline void init() { ; i<=N; i++) PushCnt[i] = , Head[i] = -, Dis[i] = INF, vis[i] = false; cnt = ; } inline void AddEdge(int from, int to, int weight) { Edge[cnt].w = weight; Edge[cnt].v = to; Edge[cnt].nxt = Head[from]; Head[from] = cnt++; } bool SPFA(int st)///若要判断负环、改为 bool { deque<int> que; que.push_back(st); vis[st]=true; Dis[st]=; while (!que.empty()) { int T=que.front(); que.pop_front(); vis[T]=false; ; i=Edge[i].nxt) { int v=Edge[i].v; int w=Edge[i].w; if (Dis[v]>Dis[T]+w){ Dis[v]=Dis[T]+w; if (!vis[v]){ if(++PushCnt[v] > N) return false; //有负环 vis[v]=true; if(!que.empty() && Dis[v] < Dis[que.front()]) que.push_front(v); else que.push_back(v); } } } } return true; } int main(void) { int nCase, W; scanf("%d", &nCase); while(nCase--){ scanf("%d %d %d", &N, &M, &W); init(); int from, to, weight; ; i<M; i++){ scanf("%d %d %d", &from, &to, &weight); AddEdge(from, to, weight); AddEdge(to, from, weight); } ; i<W; i++){ scanf("%d %d %d", &from, &to, &weight); AddEdge(from, to, -weight); } SPFA()?puts("NO"):puts("YES"); } ; }
最新文章
- Linux 内核进程管理之进程ID
- YbSoftwareFactory 代码生成插件【十四】:通过 DynamicLinq 简单实现 N-Tier 部署下的服务端数据库通用分页
- linux screen 命令详解[转]
- cf378D(stl模拟)
- NOIP 2005 青蛙过河
- instruments 教程
- XSS技巧综合
- Java初始化(成员变量)
- [Flex] ButtonBar系列——皮肤和外观设置
- 最完美解决Nginx部署ThinkPHP项目的办法
- Routing
- 基于visual Studio2013解决C语言竞赛题之0702函数设计
- thinkjs—控制器方法名不能大写
- Linux系统网络基本配置
- Elasticsearch短语搜索——match_phrase
- 利用 Win32 启动和检测 UWP App 的方法
- Mariadb修改root密码
- AWK如何打印从某一列到最后一列的内容
- node.js中path路径模块的使用
- windows后门