当前位置：网站首页>（部分不懂，笔记整理未完成）【图论】差分约束

（部分不懂，笔记整理未完成）【图论】差分约束

2022-08-02 06:01:00 【gzkeylucky】

知识点

一. 前置知识：判断负环

二.差分约束

差分约束系统即为n元一次不等式组，每个约束条件都是由两个变量作差构成的，形如x_i $ -- $x_j\leqslant c_k，目标为求出一组解可以满足所有约束条件。

x_i $ -- $x_j \leqslant c_k可变形为x_i \leqslant x_j + c_k，与最短路中三角形不等式 dis[y] \leqslant dis[x]+v 相似，于是将不等式组中的变量看作点，每个约束条件x_i $ -- $x_j \leqslant c_k 为从节点 j 向节点 i 连一条边权为 c_k 的有向边，在跑完最短路后，x_i=dis[i] 为差分约束系统中的一组解，若存在负环和终点不可达时，无解。

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；

必要时，建一个超级源点。

那么，什么时候需要建立超级原点呢？

有的时候，为了保证整个区间的连通的，就需要建立一个超级源点使得整个图是连通的。但是需要注意的是，在正常建边的时候，如果是从大指向小，这个时候我们建立超级源点的时候就也应该遵循这个原则，如果是是从小指向大的，建立超级源点的时候反过来即可。

！求解最大解用最短路，求解最小解用最长路

模板题：洛谷 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，代表一个不等式 x_c-x_{c'}\leqslant y。

输出格式

一行，n 个数，表示x_1 , x_2 \cdots x_n​ 的一组可行解，如果有多组解，请输出任意一组，无解请输出 NO。

输入输出样例

输入 #1

3 3
1 2 3
2 3 -2
1 3 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); //从超级原点开始
	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，减数放前面
	}
	for(int i=1;i<=n;++i)
	{
		add(0,i,0);  //构造超级原点
	}
	
	if(spfa() == 1) printf("NO\n");
	else 
	{
		for(int i=1;i<=n;++i)
		{
			write(dis[i]);
			putchar(' ');
		}
	}
	return 0;
}

相关练习

1. 洛谷 P1993 小 K 的农场

思路：根据题目中的“至多”，“至少”和“一样多”，可以得知以下三条式子：

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

一般在解决问题的时候，我们希望能将问题转换为一个模型，或者用一个通式来解决大量的问题。

那么在上面三个式子中，①式和②式都为不等式，可以看作是图的有向边。我们希望把两个式子转换成相同的表达方式。那么将②式两边都乘以-1，将式子转换为 b - a \leqslant -c ，与①式相似。

但是，③式为等式，那么可以看作是图的无向边，除了③式，还可以表示为 b - a=0 ，在代码实现的时候，就像建立无向边一样建立两次。

为了保证图的联通，我们需要建一个保证联通的超级原点，再从这个超级原点开始跑最短路，最后，注意一定要判断负环！

代码如下： 

#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 种树

方法一：贪心算法

思路：这道题用贪心算法很好理解。为了保证所种的树最少，那么就需要在区间重合的部分种的树越多，然而重叠部分一定在区间的尾部，所以先对区间结束的节点进行排序，然后先依次在区间的头部从前往后种树直到满足要求，对于下一个区间，看看差多少树，就在结尾补多少。

步骤如下：

1. 按结束位置排序

2. 对每个区间进行处理：从前往后扫描区间，统计已有的树的个数

若已选点超过要求个数，则continue；否则从后往前，添加缺少的覆盖点

#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) //根据尾部节点进行排序
{
	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) //从前往后搜索区间
		{
			if(vis[j]!=0) //区间中存在被标记过的点
			{
			sum++;	
			}
		}	
		if(sum >= edge[i].t) continue;
		for(int j=edge[i].e;j>=edge[i].b;--j) //从后往前搜索
		{
			if(vis[j] == 0) //重叠部分增加要种的树
			{
			vis[j]=1;
			sum++; //统计区间的数目增加
			ans++; //总数增加
			if(sum == edge[i].t) break;
			}
			
		}
		
	}
	printf("%d",ans);
	return 0;
}

 方法二：差分约束

思路：

根据题意：对于每个约束条件u \rightarrow v，最小值为w ，区间的长度可以表示为v-u+1，转换成两数之差为v-(u-1)，即 sum[v]-sum[u-1] \geqslant w ，表示在区间 \left [ u,v \right ] 之间至少有w棵树（sum[x]为x的前缀和）。又因为在每个间隔中只能选择不种或者是种1棵树，得出隐含条件： 0 \leqslant sum[v]-sum[v-1] \leqslant 1 。

在这道题中还需要注意的一点是：所建立的超级原点为n+1。根据题意，序号为1的位置是可以种树的，如果从0开始建立超级原点，可能会导致序号1的位置只能维持不种树的情况。

#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); //从超级原点开始查找
	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); //这里的超级原点是n+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); //建边方式
	}
	for(int i=1;i<=n;++i)
	{
		add(i,i-1,0);
		add(i-1,i,1);
	}
	spfa();
	write(-dis[0]); //输入的时候是负边权，输出要取反；
	return 0;
}

原网站

版权声明
本文为[gzkeylucky]所创，转载请带上原文链接，感谢
https://blog.csdn.net/gzkeylucky/article/details/126084992

边栏推荐

猜你喜欢

随机推荐