P3385 【模板】负环

2018-06-17 22:14:45来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

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

输入输出格式

输入格式:

 

第一行一个正整数T表示数据组数,对于每组数据:

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

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

 

输出格式:

 

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

 

输入输出样例

输入样例#1:
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
输出样例#1:
N0
YE5

说明

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

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

 

一开始用差分约束中判断负环的方法,。

发现会T3个点,原因很是我们的SPFA 主要是用来求最短路,其次是用来判断负环。

所以很大的一部分时间用在了最短路上,

那么我们可以放弃最短路,直接求负环。

这样的话刚开始直接把所有的dis全部赋值为0即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<algorithm>
 7 #define lli long long int 
 8 using namespace std;
 9 const int MAXN=200001;
10 const int maxn=0x7fffff;
11 inline void read(int &n)
12 {
13     char c='+';int x=0;bool flag=0;
14     while(c<'0'||c>'9')
15     {c=getchar();if(c=='-')flag=1;}
16     while(c>='0'&&c<='9')
17     {x=(x<<1)+(x<<3)+c-48;c=getchar();}
18     flag==1?n=-x:n=x;
19 }
20 int T,n,m;
21 struct node
22 {
23     int u,v,w,nxt;
24 }edge[MAXN*2];
25 int head[MAXN];
26 int num=1;
27 int dis[MAXN];
28 bool vis[MAXN];
29 bool flag=0;
30 inline void cler()
31 {
32     /*for(int i=1;i<=n;i++)
33     {
34         head[i]=-1;
35         dis[i]=maxn;
36         vis[i]=0;
37     }*/
38     memset(head,-1,sizeof(head));
39     memset(dis,0,sizeof(dis));
40     memset(vis,0,sizeof(vis));
41 //    dis[1]=0;
42     flag=0;
43     num=1;
44 }
45 inline void add_edge(int x,int y,int z)
46 {
47     edge[num].u=x;
48     edge[num].v=y;
49     edge[num].w=z;
50     edge[num].nxt=head[x];
51     head[x]=num++;
52 }
53 inline void SPFA(int now)
54 {
55     vis[now]=1;
56     for(int i=head[now];i!=-1;i=edge[i].nxt)
57     {
58         if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
59         {
60             
61                 if(vis[edge[i].v]||flag)
62                 {
63                     flag=1;
64                     break;
65                 }
66                 dis[edge[i].v]=dis[edge[i].u]+edge[i].w;    
67                 SPFA(edge[i].v);
68         }
69     }
70     vis[now]=0;
71 }
72 int main()
73 {
74     read(T);
75     while(T--)
76     {
77         //read(n);read(m);
78         scanf("%d%d",&n,&m);
79         cler();
80         for(int i=1;i<=m;i++)
81         {
82             int x,y,z;
83             scanf("%d%d%d",&x,&y,&z);
84             //read(x);read(y);read(z);
85             add_edge(x,y,z);
86             if(z>=0)
87             add_edge(y,x,z);
88         }
89         for(int i=1;i<=n;i++)
90         {
91             SPFA(i);
92             if(flag)    
93             break;
94         }
95         if(flag)printf("YE5\n");    
96             else printf("N0\n");
97     }
98     return 0;
99 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:2594 解药还是毒药

下一篇:P3382 【模板】三分法