当前位置：网站首页>(Part of it is not understood, and the notes are not completed) [Graph Theory] Difference Constraints

(Part of it is not understood, and the notes are not completed) [Graph Theory] Difference Constraints

2022-08-02 07:26:00 【gzkeylucky】

知识点

一. 前置知识：判断负环

二.差分约束

差分约束系统即为n元一次不等式组,each constraint都是由两个变量作差构成的,形如 $x_i $ -- $x_j\leqslant c_k$ ,The goal is to find a set of solutions that satisfy all constraints.

$x_i $ -- $x_j \leqslant c_k$ 可变形为 $x_i \leqslant x_j + c_k$ ,与Triangular Inequality in Shortest Path $dis[y] \leqslant dis[x]+v$ 相似,So consider the variables in the inequality group as points,each constraint $x_i $ -- $x_j \leqslant c_k$ 为从节点 j 向节点 i 连一条边权为的有向边,After running the most short circuit, x_i=dis[i] is a set of solutions in a differentially constrained system,若When there exists negative ring and destination unreachable,无解.

$x_i - x_j \geqslant c_k$ 变形为 $x_j - x_i\leqslant - c_k$ ;

x_i $ -- $x_j < c_k 变形为 $x_i $ -- $x_j \leq c_k - 1$ ;

x_i - x_j> c_k 变形为 $x_i-x_j \geqslant c_k+1$ ;

x_i - x_j=c_k 变形为 $x_i - x_j \leqslant 0$ 且 $x_i - x_j \geqslant 0$ ;

必要时,建一个超级源点.

那么,When do you need to create a super origin?？

有的时候,In order to ensure the connectivity of the entire range,Just need to build a super source point makes the whole graph is connected.但是需要注意的是,During normal construction,If it is from big to small,At this time, we should also follow this principle when creating a super source point,If it is from small to large,When creating a super source point, it can be reversed.

！Find the maximum solution using the shortest path,Find the smallest solution using the longest path

模板题：洛谷 P5960 【模板】差分约束算法

题目描述

给出一组包含 m 个不等式,有 n 个未知数的形如：

$\begin{cases} x_{c_1}-x_{c'_1}\leqslant y_1 \\x_{c_2}-x_{c'_2} \leqslant y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leqslant y_m\end{cases}$

的不等式组,求任意一组满足这个不等式组的解.

输入格式

第一行为两个正整数 n,m,代表未知数的数量和不等式的数量.

接下来 m 行,每行包含三个整数 c,c′,y,On behalf of an inequality $x_c-x_{c'}\leqslant y$ .

输出格式

一行,n 个数,表示 $x_1 , x_2 \cdots x_n$ 的一组可行解,如果有多组解,Please output any group,无解请输出 NO.

输入输出样例

输入 #1

输出 #1

5 3 5

说明/提示

样例解释

$\begin{cases}x_1-x_2\leqslant 3 \\ x_2 - x_3 \leqslant -2 \\ x_1 - x_3 \leqslant 1 \end{cases}$

一种可行的方法是 x_1 = 5 , x_2=3 , x_3=5 .

$\begin{cases}5-3 = 2\leqslant 3 \\ 3 - 5=-2 \leqslant -2 \\ 5 - 5=0\leqslant 1 \end{cases}$

数据范围

对于 100% 的数据, $1\leqslant n,m \leqslant 5\times 10^3$ , $-10^4\leqslant y \leqslant 10^4$ , $1\leqslant c,c' \leqslant n$ , $c \neq c'$ .

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
int n,m;
const int maxn=1e7+5,INF=0x3f3f3f3f;
struct node{
	int to,next,w;
}edge[maxn<<1];
int head[maxn],num=0,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()
{
	memset(dis,INF,sizeof(dis));
	memset(ans,0,sizeof(ans));
	memset(vis,0,sizeof(vis));
	q.push(0); //from super origin
	vis[0]=1;
	dis[0]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		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+1)
				{
					return 1;
				}
				
				if(!vis[v]) 
				{
				vis[v]=1;
				q.push(v);
				}
			}
		}
	}
	return 0;
}

int main()
{
	n=read(); m=read();
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;++i)
	{
		int a=read(),b=read(),y=read();
		add(b,a,y);  //要注意从b到a,Minus in front
	}
	for(int i=1;i<=n;++i)
	{
		add(0,i,0);  //Construct the super origin
	}
	
	if(spfa() == 1) printf("NO\n");
	else 
	{
		for(int i=1;i<=n;++i)
		{
			write(dis[i]);
			putchar(' ');
		}
	}
	return 0;
}

相关练习

1. 洛谷 P1993 小 K 的农场

思路：According to the topic of“至多”,“至少”和“一样多”,The following three equations can be obtained：

$\begin{cases} a-b \leqslant c\\ a - b \geqslant c \\ a-b = c \end{cases}$

Usually when solving problems,We want to be able to convert the problem into a model,Or use a general formula to solve a large number of problems.

Then in the above three equations,①式和②are inequalities,can be viewed as a directed edge of the graph.We want to convert both expressions into the same expression.那么将②multiply both sides by-1,Convert the formula to $b - a \leqslant -c$ ,与①式相似.

但是,③Equation,Then it can be regarded as an undirected edge of the graph,除了③式,还可以表示为 b - a=0 ,在代码实现的时候,build twice as if building an undirected edge.

In order to ensure the connectivity of the graph,We need to build a super origin that guarantees connectivity,Then start from this super origin and run the shortest path,最后,Be careful to judge the negative ring！

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
int n,m;
const int maxn=1e7+5,INF=0x3f3f3f3f;
struct node{
	int to,next,w;
}edge[maxn<<1];
int head[maxn],num=0,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 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()
{
	memset(dis,INF,sizeof(dis));
	memset(ans,0,sizeof(ans));
	memset(vis,0,sizeof(vis));
	q.push(0);
	vis[0]=1;
	dis[0]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		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(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
				if(ans[v]==n)
				{
					return 0;
				}
				
				
			}
		}
	} 
	return 1;
}

int main()
{
	n=read(); m=read();
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;++i)
	{
		add(0,i,0);
	}
	
	for(int i=1;i<=m;++i)
	{
		int num=read();
		int a,b,c;
		if(num == 1) //a-b<=c的情况
		{
			a=read(),b=read(),c=read();
			add(a,b,-c);
		}
		else if(num == 2) //a-b >= c的情况
		{
			a=read(),b=read(),c=read();
			add(b,a,c);
		}
		else
		{
			a=read(),b=read();
			add(a,b,0);
			add(b,a,0);
		}
	}
	
	if(spfa()== 1) printf("Yes");
	else printf("No");
	return 0;
}

2. 洛谷 P1250 种树

方法一：贪心算法

思路：This problem is well understood by greedy algorithm.In order to ensure the minimum number of trees planted,Then the more trees that need to be planted in the overlapping part of the interval,However, the overlapping part must be at the end of the interval,So first sort the nodes at the end of the interval,Then first plant trees at the head of the interval from front to back until the requirements are met,对于下一个区间,See how many trees are missing,how much at the end.

步骤如下：

1. Sort by end position

2. process each interval：Scan the interval from front to back,Count the number of existing trees

If the number of selected points exceeds the required number,则continue;Or from the back forward,Add the missing points

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
int n,h,ans=0;
const int maxn=1e7+5;
bool vis[maxn];
struct node{
	int b,e,t;
}edge[maxn<<1];

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 bool cmp(node x,node y) //According to the end node
{
	return x.e<y.e;
}

int main()
{
	n=read(); h=read();
	for(int i=1;i<=h;++i)
	{
		edge[i].b=read();
		edge[i].e=read();
		edge[i].t=read();
	}
	sort(edge+1,edge+h+1,cmp);
	memset(vis,0,sizeof(vis));

	for(int i=1;i<=h;++i)
	{
		int sum=0;
		for(int j=edge[i].b;j<=edge[i].e;++j) //Once upon a time in the future search range
		{
			if(vis[j]!=0) //There are marked points in the interval
			{
			sum++;	
			}
		}	
		if(sum >= edge[i].t) continue;
		for(int j=edge[i].e;j>=edge[i].b;--j) //从后往前搜索
		{
			if(vis[j] == 0) //Add the tree to be planted in the overlapping part
			{
			vis[j]=1;
			sum++; //The number of statistical intervals increases
			ans++; //总数增加
			if(sum == edge[i].t) break;
			}
			
		}
		
	}
	printf("%d",ans);
	return 0;
}

方法二：差分约束

思路：

根据题意：对于each constraint $u \rightarrow v$ ,最小值为w ,The length of the interval can be expressed as v-u+1 ,Convert the difference between two numbers to v-(u-1) ,即 $sum[v]-sum[u-1] \geqslant w$ ,表示在区间 $\left [ u,v \right ]$ 之间至少有w棵树（sum[x]为x的前缀和）.And because in each interval can only choose different species or species1棵树,get the implicit condition： $0 \leqslant sum[v]-sum[v-1] \leqslant 1$ .

Another point to note in this question is that：The established super origin isn+1.根据题意,序号为1The location is where trees can be planted,如果从0Start building a super origin,may result in serial number1The location can only be maintained without tree planting.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
int n,h;
const int maxn=1e7+5,INF=0x3f3f3f3f;
struct node
{
	int to,next,w;
}edge[maxn<<1];
int head[maxn],num=0,dis[maxn];
struct node1
{
	int b,e,t;
}edge1[maxn<<1];
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()
{
	memset(dis,INF,sizeof(dis));
	q.push(n+1); //Starting from the origin of the super lookup
	vis[n+1]=1;
	dis[n+1]=0; 
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		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;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return 0;
}

int main()
{
	n=read(); h=read();
	memset(head,-1,sizeof(head));
	for(int i=0;i<=n;++i)
	{
		add(n+1,i,0); //The super origin here isn+1 
	}
	
	for(int i=1;i<=h;++i)
	{
		edge1[i].b=read();
		edge1[i].e=read();
		edge1[i].t=read();
		add(edge1[i].e,edge1[i].b-1,-edge1[i].t); //Edge construction
	}
	for(int i=1;i<=n;++i)
	{
		add(i,i-1,0);
		add(i-1,i,1);
	}
	spfa();
	write(-dis[0]); //When input is a negative side,output to be negated;
	return 0;
}

原网站

版权声明
本文为[gzkeylucky]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/214/202208020601064621.html