【luogu P3385 负环】 模板
2024-08-28 01:53:31
题目链接:https://www.luogu.org/problemnew/show/P3385
SPFA判负环。
这个题必须卡一卡才过得去。
按理说对于一个负环点应当是入队 > n次。
但是这个题数据不是很友好qwq
所以我们把入队次数变成 >= (n/4)次。
到考试的时候你说是写 > n 还是 > (n/4) ?
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10000 + 10;
const int inf = 0x7fffffff;
struct edge{
int from, to, next, len;
}e[maxn<<2];
int head[maxn], cnt, visnum[maxn], dis[maxn];
int vis[maxn];
queue<int> q;
int T, n, m;
void add(int u, int v, int w)
{
e[++cnt].from = u;
e[cnt].len = w;
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt;
}
bool SPFA()
{
while(!q.empty())
{
int now = q.front();q.pop();
vis[now] = 0;
for(int i = head[now]; i != -1; i = e[i].next)
{
if(dis[e[i].to] > dis[now] + e[i].len)
{
dis[e[i].to] = dis[now] + e[i].len;
if(!vis[e[i].to])
{
visnum[e[i].to]++;
if(visnum[e[i].to] >= (n>>2)) return 1;
q.push(e[i].to);
}
}
}
}
return 0;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
cnt = 0;
while(!q.empty()) q.pop();
memset(visnum,0,sizeof(visnum));
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
memset(e,0,sizeof(e));
for(int i = 1; i <= n; i++) dis[i] = inf;
for(int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d%d%d",&u,&v,&w);
if(w >= 0)
{
add(u, v, w); add(v, u, w);
}
if(w < 0)
{
add(u, v, w);
}
}
int s = 1;
q.push(s); dis[s] = 0; vis[s] = 1;
if(SPFA())
printf("YE5\n");
else
printf("N0\n");
}
return 0;
}
最新文章
- setTimeout()与setInterval()——走马灯效果
- WCF的一点补充-Restful相关
- 初学Java语法(笔记)
- Django忘记管理员账号和密码的解决办法
- 解读Hashtable
- Spring 3整合Quartz 2实现定时任务--转
- 浅谈JS数据类型存储问题
- hive 分配map数过少导致任务执行慢
- SpringMVC的视图解析器
- 【G】开源的分布式部署解决方案文档 - 手动安装
- 腾讯云主机 MySQL 远程访问配置方法
- 通过js添加的元素点击事件无法触发
- vue webpack打包
- 手动用tomcat启动war包,无法访问web项目
- numpy中 array数组的shape属性
- oracle中的decode的使用(转)
- C# List left join
- C#编程(三十六)----------元组
- Delphi泛型动态数组的扩展--转贴
- BZOJ 2742: [HEOI2012]Akai的数学作业
热门文章
- 015-GenericEncodingFilter模板【解决全局乱码】
- nyoj 349&;Poj 1094 Sorting It All Out——————【拓扑应用】
- bzoj 3576: [Hnoi2014]江南乐
- 上下文(Context)和作用域(Scope)
- linux安装lua_nginx_module模块
- sql查询结果多对多转为一对多返回前端
- hiveQL随笔
- Spring课程 Spring入门篇 4-9 Spring bean装配之对jsr支持的说明
- Cannot execute request on any known server
- Java集合篇六:Map中key值不可重复的测试