P3385 【模板】负环
2018-06-17 22:14:45来源:未知 阅读 ()
题目描述
暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索
输入输出格式
输入格式:
第一行一个正整数T表示数据组数,对于每组数据:
第一行两个正整数N M,表示图有N个顶点,M条边
接下来M行,每行三个整数a b w,表示a->b有一条权值为w的边(若w<0则为单向,否则双向)
输出格式:
共T行。对于每组数据,存在负环则输出一行"YE5"(不含引号),否则输出一行"N0"(不含引号)。
输入输出样例
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
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 【模板】三分法
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 单调队列模板【附例题】 2020-05-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash