题目描述
暴力枚举/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
spfa判负环模板
判断有无负环:如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)
代码:
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 200010 using namespace std; bool vis[N],vist; int n,m,t,x,y,z,tot,head[N],dis[N]; int read() { ,f=; char ch=getchar(); ; ch=getchar();} +ch-'; ch=getchar();} return x*f; } struct Edge { int to,dis,from,next; }edge[N<<]; int add(int x,int y,int z) { tot++; edge[tot].to=y; edge[tot].dis=z; edge[tot].next=head[x]; head[x]=tot; } void begin() { tot=vist=; memset(dis,,sizeof(dis)); memset(head,,sizeof(head)); memset(vis,false,sizeof(vis)); } int spfa(int s) { vis[s]=true; for(int i=head[s];i;i=edge[i].next) { int t=edge[i].to; if(dis[s]+edge[i].dis<dis[t]) { dis[t]=dis[s]+edge[i].dis; if(vis[t]||vist) { vist=true; break; } spfa(t); } } vis[s]=false; } int main() { t=read(); while(t--) { n=read(),m=read();begin(); ;i<=m;i++) { x=read(),y=read(),z=read(); add(x,y,z); ) add(y,x,z); } ;i<=n;i++) { spfa(i); if(vist) break; } if(vist) printf("YE5\n"); else printf("N0\n"); } ; }