锐客网

  1. 首页 > it技术 > >

usaco|BZOJ 1715: [Usaco2006 Dec]Wormholes 虫洞

【usaco|BZOJ 1715: [Usaco2006 Dec]Wormholes 虫洞】 spfa 判断负环
当某一个点被更新次数 ≥n 就表示有负环
直接 spfa 果上就好了

#include #include #include #define g getchar() #define ll long long #define inf 0x3f3f3f3f using namespace std; inline ll read(){ ll x=0,f=1; char ch=g; for(; ch<'0'||ch>'9'; ch=g)if(ch=='-')f=-1; for(; ch>='0'&&ch<='9'; ch=g)x=x*10+ch-'0'; return x*f; } inline void out(ll x){ int a[25],wei=0; if(x<0)putchar('-'),x=-x; for(; x; x/=10)a[++wei]=x%10; if(wei==0){puts("0"); return; } for(int j=wei; j>=1; --j)putchar('0'+a[j]); putchar('\n'); } struct re{int v,w,next; }ed[7005]; int dui[2500*500+5],dis[2505],n,head[2505],F,m,mm,e,inq[2505]; bool pd[2505],fl; int clear(){ memset(dis,inf,sizeof(dis)); memset(inq,0,sizeof(inq)); memset(pd,0,sizeof(pd)); memset(head,0,sizeof(head)); fl=0; e=0; } inline int ins(int x,int y,int w){ed[++e]=(re){y,w,head[x]}; head[x]=e; } int spfa(int x){ int tou=1,wei=1; dui[1]=x; if(inq[x])return 0; memset(inq,0,sizeof(inq)); memset(dis,inf,sizeof(dis)); inq[x]=1; dis[x]=0; for(; tou<=wei; pd[dui[tou++]]=0){ int u=dui[tou]; if(inq[u]>n){fl=1; return 0; } for(int i=head[u]; i; i=ed[i].next){ int v=ed[i].v; if(dis[v]>dis[u]+ed[i].w){ dis[v]=dis[u]+ed[i].w; ++inq[v]; if(!pd[v])dui[++wei]=v,pd[v]=1; } } } if(dis[x]<0)fl=1; return 0; } int main(){ //freopen("","r",stdin); //freopen("","w",stdout); F=read(); for(; F--; ){ clear(); n=read(); m=read(); mm=read(); for(int i=1; i<=m; ++i){int x=read(),y=read(),w=read(); ins(x,y,w); ins(y,x,w); } for(int i=1; i<=mm; ++i){int x=read(),y=read(),w=read(); ins(x,y,-w); } for(int i=1; i<=n; ++i){if(fl)break; spfa(i); } puts(fl?"YES":"NO"); } return 0; }

    推荐阅读


    上一篇：1000:A+B Problem

    下一篇：bzoj|BZOJ 4325: NOIP2015 斗地主