Negative ring

Knowledge point

---

Negative loop , seeing the name of a thing one thinks of its function , It is a ring with a negative sum of edge weights on a graph .

The negative weight edge is on the shortest path or such problems , It will lead to the failure of some algorithms that can work normally on the positive weight graph . 

  Deal with negative edge weights , May adopt Flody Algorithm ,Bellman-Ford Algorithm , And optimized Bellman-Ford Algorithm ：SPFA

  In the competition , Most topics will be stuck SPFA Algorithm , But encounter existence Negative edge right When ,SPFA The algorithm is the positive solution .

 SPFA Algorithm core code ：

queue <int> q;
inline bool SPFA()
{	
	memset(dis,INF,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(ans,0,sizeof(ans));
    // An array of zero 
	while(!q.empty()) q.pop(); // Clear queue 
	q.push(1); // Join the node first , Then record 
	dis[1]=0; // Record path 
	vis[1]=1; // Statistics show that this point has been searched 
	while(!q.empty())
	{
		int u=q.front(); // Take out the team leader element 
		vis[u]=0; // Mark the point 
		q.pop(); // Pop up this point 
		for(int i=head[u];i!=-1;i=edge[i].next) // The way to find each point with a chained forward star 
		{
		int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].w) // Slack operation 
			{
				dis[v]=dis[u]+edge[i].w; 
				ans[v]=ans[u]+1; // Count the paths that have been taken 
				if(ans[v]>=n) // The number of paths is greater than n, The point of existence is passed for the second time 
				{
				return 1;		
				}
				if(!vis[v])  // If the point of arrival is not in the queue 
				{	
				q.push(v); // Enter the next point into the team 
				vis[v]=1;
				}
			}
		}
	}
	return 0;  // No negative ring 
}

---

  The template questions ： Luogu P3385 【 Templates 】 Negative loop

Title Description

Given a  n  A digraph with two points , Request whether there is From the top  1  Departure can reach Negative ring of .

The definition of a negative ring is ： A loop in which the sum of edge weights is negative .

Input format

There are multiple groups of test data at the test point of this question sheet .

The first line of input is an integer  T, Number of groups representing test data . The format of each group of data is as follows ：

The first line has two integers , Respectively represent the number of points of the graph  n  And the number of pieces of edge information given next  m.

Next  m  That's ok , Three integers per row u,v,w.

• if w ≥ 0, Then it means that there is a line from  u  to  v  The boundary right is  w  The edge of , There is also a way from  v  to  u  The boundary right is  w  The edge of .
• if w < 0, Then it only means that there is a line from  u  to  v  The boundary right is  w  The edge of .

Output format

For each set of data , Output a string one line , If the negative ring exists , The output  YES, Otherwise output  NO.

I/o sample

Input #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

Output #1

NO
YES

explain / Tips

Data scale and agreement

For all test points , Guarantee ：

• 1≤n≤2×10^3,1≤m≤3×10^3.
• 1≤ u , v ≤n,−10^4≤w≤10^4.
• 1≤T≤10.

Tips

Please note that ,m  No The number of sides of a graph .

---

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
int t,n,m;
const int maxn=1e7+5,INF=0x3f3f3f3f;
struct node{
	int to,next,w;
}edge[maxn<<1];

int num=0,dis[maxn],head[maxn],ans[maxn];
bool vis[maxn];
queue <int> q;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void add(int u,int v,int w)
{
	edge[++num].to=v;
	edge[num].w=w;
	edge[num].next=head[u];
	head[u]=num;
}

inline void bellman_ford()
{	
	memset(dis,INF,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(ans,0,sizeof(ans));
    // An array of zero 
	while(!q.empty()) q.pop(); // Clear queue 
	q.push(1); // Join the node first , Then record 
	dis[1]=0; // Record path 
	vis[1]=1; // Statistics show that this point has been searched 
	while(!q.empty())
	{
		int u=q.front(); // Take out the team leader element 
		vis[u]=0; // Mark the point 
		q.pop();
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
		int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].w) // Slack operation 
			{
				dis[v]=dis[u]+edge[i].w; 
				ans[v]=ans[u]+1; // Count the paths that have been taken 
				if(ans[v]>=n) // The number of paths is greater than n, The point of existence is passed for the second time 
				{
				printf("YES\n");
				return;		
				}
				if(!vis[v])  // If the point of arrival is not in the queue 
				{	
				q.push(v); // Enter the next point into the team 
				vis[v]=1;
				}
			}
		}
	}
	printf("NO\n");  // No negative ring 
}

int main()
{	
	t=read();
	for(int k=1;k<=t;++k)
	{
		n=read(); m=read();
		memset(head,-1,sizeof(head));
		for(int i=1;i<=m;++i)
		{
			int u=read(),v=read(),w=read();
			if(w>=0) 
			{
				add(u,v,w);
				add(v,u,w);
			}
			else add(u,v,w);
		}
		
		bellman_ford();
		
	}
	return 0;
}

---

Related exercises ：

1 .  Luogu P2136 Close up

Details to note ：

1. It can be downloaded from 1 Start looking for , You can also get it from n Start looking for , That is, you can traverse the graph twice .

2. In the process of traversal , As long as there is a negative ring , It outputs “Forever love”.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
int n,m;
const int maxn=1e5+5,INF=0x3f3f3f3f;
struct node{
	int to,next,w;
}edge[maxn<<1];
int num=0,head[maxn],dis[maxn],ans[maxn];
bool vis[maxn];
queue <int> q;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

inline void add(int u,int v,int w)
{
	edge[++num].to=v;
	edge[num].w=w;
	edge[num].next=head[u];
	head[u]=num;
}

inline bool SPFA(int x)
{
	memset(dis,INF,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(ans,0,sizeof(ans));
	while(!q.empty()) q.pop();
	q.push(x);
	vis[x]=1;
	dis[x]=0;
	while(!q.empty())
	{
		int u=q.front();
		vis[u]=0;
		q.pop();
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].w)
			{
				dis[v]=dis[u]+edge[i].w;
				ans[v]=ans[u]+1;
				if(ans[v]>=n) 
				{
					return 1;
				}
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return 0;
}

int main()
{
	n=read(); m=read();
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;++i)
	{
		int s=read(),t=read(),w=read();
		add(s,t,-w); // According to the title conditions , The distance will be reduced , The distance is the opposite 
	}

	bool check=SPFA(1);
	int road=dis[n];
	bool check2=SPFA(n);
    // It can be downloaded from 1 Start looking for , You can also get it from n Start looking for 
	if(check == 1 || check2 == 1) printf("Forever love"); // As long as there is a negative ring on one side 
	else write(min(dis[1],road));
	return 0;
}