首页 > 代码库 > 洛谷—— P3385 【模板】负环

洛谷—— P3385 【模板】负环

2024-09-23 18:17:42   215人阅读

https://www.luogu.org/problem/show?pid=3385#sub

题目描述

暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索

输入输出格式

输入格式：

 

第一行一个正整数T表示数据组数，对于每组数据：

第一行两个正整数N M，表示图有N个顶点，M条边

接下来M行，每行三个整数a b w，表示a->b有一条权值为w的边（若w<0则为单向，否则双向）

 

输出格式：

 

共T行。对于每组数据，存在负环则输出一行"YE5"(不含引号)，否则输出一行"N0"(不含引号)。

 

输入输出样例

输入样例#1：
23 41 2 21 3 42 3 13 1 -33 31 2 32 3 43 1 -8
输出样例#1：
N0YE5

说明

N,M,|w|≤200 000；1≤a,b≤N；T≤10 建议复制输出格式中的字符串。

此题普通Bellman-Ford或BFS-SPFA会TLE

 

不能用百分数，就用电风扇~~~

技术分享

 

 1 #include <algorithm> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue>  5  6 using namespace std; 7  8 const int N(200000+5); 9 int t,n,m,u,v,w;10 int sumedge,head[N];11 struct Edge12 {13     int to,next,cost;14     Edge(int to=0,int next=0,int cost=0):15         to(to),next(next),cost(cost) {}16 }edge[N<<1];17 18 void ins(int from,int to,int cost)19 {20     /*++sumedge;21     edge[sumedge].to=to;22     edge[sumedge].next=head[from];23     edge[sumedge].cost=cost;*/24     edge[++sumedge]=Edge(to,head[from],cost);25     head[from]=sumedge;26 }27 28 int dis[N],vis[N],if_;29 30 void SPFA(int now)31 {32     vis[now]=1;33     for(int i=head[now];i;i=edge[i].next)34     {35         int go=edge[i].to;36         if(dis[go]>dis[now]+edge[i].cost)37         {38             if(vis[go]||if_)39             {40                 if_=1;41                 break;42             }43             dis[go]=dis[now]+edge[i].cost;44             SPFA(go);45         }46     }47     vis[now]=0;48 }49 50 void init()51 {52     memset(dis,0,sizeof(dis));53     memset(vis,0,sizeof(vis));54     memset(head,0,sizeof(head));55     if_=sumedge=0;56 }57 58 int main()59 {60     scanf("%d",&t);61     for(;t;t--)62     {63         scanf("%d%d",&n,&m);64         init();65         for(int i=1;i<=m;i++)66         {67             scanf("%d%d%d",&u,&v,&w);68             ins(u,v,w);69             if(w>=0) ins(v,u,w);70         }71         for(int i=1;i<=n;i++)72         {73             SPFA(i);74             if(if_) break;75         }76         if(if_) printf("YE5\n");77         else printf("N0\n");78     }    79     return 0;80 }

 

洛谷—— P3385 【模板】负环


联系
我们