模板+解题报告：luogu P3385 【模板】负环

题目链接:P3385 【模板】负环

缩点板子。

看日报上说\(DFS\)会炸（我确实打炸了），就根据他的说明\(yy\)了\(BFS\)，多一个记录步数的数组即可（我用的\(len[]\)），若\(len_i>n\)，就说明遁入无限的负环中了，返回即可，跑得比我那一页快人均\(200ms\)的样子（没有卡常）（其实一堆Unshown）.

\(Code\):

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int inf=1e9;

int t,n,m,l,r,s;

int vis[2005],dis[2005];

int ans=0;

int len[2005];

struct node

{

	int to,nxt,w;

}e[2005<<1];

int head[2005],cnt=0;

queue<int> q;

void init(int n)

{

	while(!q.empty()) q.pop();

	memset(vis,0,sizeof(vis));

	memset(e,0,sizeof(e));

	memset(head,0,sizeof(head));

	for(int i=2;i<=n;i++) dis[i]=inf;

	dis[1]=0;

	vis[1]=1;

	len[1]=0;

	cnt=0;

}

void add(int u,int v,int c)

{

	e[++cnt].to=v;

	e[cnt].nxt=head[u];

	e[cnt].w=c;

	head[u]=cnt;

}

bool spfa()

{

	q.push(1);

	while(!q.empty())

	{

		int k=q.front();

		q.pop();

		vis[k]=0;

		for(int i=head[k];i;i=e[i].nxt)

		{

			int j=e[i].to;

			if(dis[j]>dis[k]+e[i].w)

			{

				dis[j]=dis[k]+e[i].w;

				len[j]=len[k]+1;

				if(len[j]>n) return true;

				if(!vis[j]) vis[j]=1,q.push(j);

			}

		}

	}

	return false;

}

int main()

{

	scanf("%d",&t);

	while(t--)

	{

		scanf("%d%d",&n,&m);

		init(n);

		for(int i=1;i<=m;i++)

		{

			scanf("%d%d%d",&l,&r,&s);

			add(l,r,s);

			if(s>=0) add(r,l,s);

		}

		if(spfa()) printf("YE5\n");

		else printf("N0\n");

	}

	return 0;

}

吐槽一下，这个“YE5”是啥鬼？考验抠字眼耶......

巴特西

模板+解题报告：luogu P3385 【模板】负环

\(Code\):

最新文章

热门文章