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

    知识点

    一. 前置知识：判断负环

    二.差分约束

    差分约束系统即为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'。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. using namespace std;
    8. int n,m;
    9. const int maxn=1e7+5,INF=0x3f3f3f3f;
    10. struct node{
    11. 	int to,next,w;
    12. }edge[maxn<<1];
    13. int head[maxn],num=0,dis[maxn],ans[maxn];
    14. bool vis[maxn];
    15. queue <int> q;
    16. inline int read()
    17. {
    18. 	int x=0,f=1;
    19. 	char c=getchar();
    20. 	while(c<'0'||c>'9')
    21. 	{
    22. 		if(c=='-') f=-1;
    23. 		c=getchar();
    24. 	}
    25. 	while(c>='0'&&c<='9')
    26. 	{
    27. 		x=(x<<3)+(x<<1)+(c^48);
    28. 		c=getchar();
    29. 	}
    30. 	return x*f;
    31. }
    32.  
    33. inline void write(int x)
    34. {
    35. 	if(x<0) putchar('-'),x=-x;
    36. 	if(x>9) write(x/10);
    37. 	putchar(x%10+'0');
    38. }
    39.  
    40. inline void add(int u,int v,int w)
    41. {
    42. 	edge[++num].to=v;
    43. 	edge[num].w=w;
    44. 	edge[num].next=head[u];
    45. 	head[u]=num;
    46. }
    47.  
    48. inline bool spfa()
    49. {
    50. 	memset(dis,INF,sizeof(dis));
    51. 	memset(ans,0,sizeof(ans));
    52. 	memset(vis,0,sizeof(vis));
    53. 	q.push(0); //从超级原点开始
    54. 	vis[0]=1;
    55. 	dis[0]=0;
    56. 	while(!q.empty())
    57. 	{
    58. 		int u=q.front();
    59. 		q.pop();
    60. 		vis[u]=0;
    61. 		for(int i=head[u];i!=-1;i=edge[i].next)
    62. 		{
    63. 			int v=edge[i].to;
    64. 			if(dis[v]>dis[u]+edge[i].w)
    65. 			{
    66. 				dis[v]=dis[u]+edge[i].w;
    67. 				ans[v]=ans[u]+1;
    68. 				if(ans[v] >= n+1)
    69. 				{
    70. 					return 1;
    71. 				}
    72. 				
    73. 				if(!vis[v]) 
    74. 				{
    75. 				vis[v]=1;
    76. 				q.push(v);
    77. 				}
    78. 			}
    79. 		}
    80. 	}
    81. 	return 0;
    82. }
    83.  
    84. int main()
    85. {
    86. 	n=read(); m=read();
    87. 	memset(head,-1,sizeof(head));
    88. 	for(int i=1;i<=m;++i)
    89. 	{
    90. 		int a=read(),b=read(),y=read();
    91. 		add(b,a,y);  //要注意从b到a，减数放前面
    92. 	}
    93. 	for(int i=1;i<=n;++i)
    94. 	{
    95. 		add(0,i,0);  //构造超级原点
    96. 	}
    97. 	
    98. 	if(spfa() == 1) printf("NO\n");
    99. 	else 
    100. 	{
    101. 		for(int i=1;i<=n;++i)
    102. 		{
    103. 			write(dis[i]);
    104. 			putchar(' ');
    105. 		}
    106. 	}
    107. 	return 0;
    108. }

    相关练习

    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 ，在代码实现的时候，就像建立无向边一样建立两次。

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

    代码如下： 

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. using namespace std;
    8. int n,m;
    9. const int maxn=1e7+5,INF=0x3f3f3f3f;
    10. struct node{
    11. 	int to,next,w;
    12. }edge[maxn<<1];
    13. int head[maxn],num=0,dis[maxn],ans[maxn];
    14. bool vis[maxn];
    15. queue <int> q;
    16. inline int read()
    17. {
    18. 	int x=0,f=1;
    19. 	char c=getchar();
    20. 	while(c<'0'||c>'9')
    21. 	{
    22. 		if(c=='-') f=-1;
    23. 		c=getchar();
    24. 	}
    25. 	while(c>='0'&&c<='9')
    26. 	{
    27. 		x=(x<<3)+(x<<1)+(c^48);
    28. 		c=getchar();
    29. 	}
    30. 	return x*f;
    31. }
    32.  
    33. inline void add(int u,int v,int w)
    34. {
    35. 	edge[++num].to=v;
    36. 	edge[num].w=w;
    37. 	edge[num].next=head[u];
    38. 	head[u]=num;
    39. }
    40.  
    41. inline bool spfa()
    42. {
    43. 	memset(dis,INF,sizeof(dis));
    44. 	memset(ans,0,sizeof(ans));
    45. 	memset(vis,0,sizeof(vis));
    46. 	q.push(0);
    47. 	vis[0]=1;
    48. 	dis[0]=0;
    49. 	while(!q.empty())
    50. 	{
    51. 		int u=q.front();
    52. 		q.pop();
    53. 		vis[u]=0;
    54. 		for(int i=head[u];i!=-1;i=edge[i].next)
    55. 		{
    56. 			int v=edge[i].to;
    57. 			if(dis[v]>dis[u]+edge[i].w)
    58. 			{
    59. 				dis[v]=dis[u]+edge[i].w;
    60. 				ans[v]=ans[u]+1;
    61. 				if(!vis[v])
    62. 				{
    63. 					q.push(v);
    64. 					vis[v]=1;
    65. 				}
    66. 				if(ans[v]==n)
    67. 				{
    68. 					return 0;
    69. 				}
    70. 				
    71. 				
    72. 			}
    73. 		}
    74. 	} 
    75. 	return 1;
    76. }
    77.  
    78. int main()
    79. {
    80. 	n=read(); m=read();
    81. 	memset(head,-1,sizeof(head));
    82. 	for(int i=1;i<=n;++i)
    83. 	{
    84. 		add(0,i,0);
    85. 	}
    86. 	
    87. 	for(int i=1;i<=m;++i)
    88. 	{
    89. 		int num=read();
    90. 		int a,b,c;
    91. 		if(num == 1) //a-b<=c的情况
    92. 		{
    93. 			a=read(),b=read(),c=read();
    94. 			add(a,b,-c);
    95. 		}
    96. 		else if(num == 2) //a-b >= c的情况
    97. 		{
    98. 			a=read(),b=read(),c=read();
    99. 			add(b,a,c);
    100. 		}
    101. 		else
    102. 		{
    103. 			a=read(),b=read();
    104. 			add(a,b,0);
    105. 			add(b,a,0);
    106. 		}
    107. 	}
    108. 	
    109. 	if(spfa()== 1) printf("Yes");
    110. 	else printf("No");
    111. 	return 0;
    112. }

    2. 洛谷 P1250 种树

    方法一：贪心算法

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

    步骤如下：

    1. 按结束位置排序

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

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

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. using namespace std;
    8. int n,h,ans=0;
    9. const int maxn=1e7+5;
    10. bool vis[maxn];
    11. struct node{
    12. 	int b,e,t;
    13. }edge[maxn<<1];
    14.  
    15. inline int read()
    16. {
    17. 	int x=0,f=1;
    18. 	char c=getchar();
    19. 	while(c<'0'||c>'9')
    20. 	{
    21. 		if(c=='-') f=-1;
    22. 		c=getchar();
    23. 	}
    24. 	while(c>='0' && c<='9')
    25. 	{
    26. 		x=(x<<3)+(x<<1)+(c^48);
    27. 		c=getchar();
    28. 	}
    29. 	return x*f;
    30. }
    31.  
    32. inline bool cmp(node x,node y) //根据尾部节点进行排序
    33. {
    34. 	return x.e
    35. }
    36.  
    37. int main()
    38. {
    39. 	n=read(); h=read();
    40. 	for(int i=1;i<=h;++i)
    41. 	{
    42. 		edge[i].b=read();
    43. 		edge[i].e=read();
    44. 		edge[i].t=read();
    45. 	}
    46. 	sort(edge+1,edge+h+1,cmp);
    47. 	memset(vis,0,sizeof(vis));
    48.  
    49. 	for(int i=1;i<=h;++i)
    50. 	{
    51. 		int sum=0;
    52. 		for(int j=edge[i].b;j<=edge[i].e;++j) //从前往后搜索区间
    53. 		{
    54. 			if(vis[j]!=0) //区间中存在被标记过的点
    55. 			{
    56. 			sum++;	
    57. 			}
    58. 		}	
    59. 		if(sum >= edge[i].t) continue;
    60. 		for(int j=edge[i].e;j>=edge[i].b;--j) //从后往前搜索
    61. 		{
    62. 			if(vis[j] == 0) //重叠部分增加要种的树
    63. 			{
    64. 			vis[j]=1;
    65. 			sum++; //统计区间的数目增加
    66. 			ans++; //总数增加
    67. 			if(sum == edge[i].t) break;
    68. 			}
    69. 			
    70. 		}
    71. 		
    72. 	}
    73. 	printf("%d",ans);
    74. 	return 0;
    75. }

     方法二：差分约束

    思路：

    根据题意：对于每个约束条件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的位置只能维持不种树的情况。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. using namespace std;
    8. int n,h;
    9. const int maxn=1e7+5,INF=0x3f3f3f3f;
    10. struct node
    11. {
    12. 	int to,next,w;
    13. }edge[maxn<<1];
    14. int head[maxn],num=0,dis[maxn];
    15. struct node1
    16. {
    17. 	int b,e,t;
    18. }edge1[maxn<<1];
    19. bool vis[maxn];
    20. queue <int> q;
    21.  
    22. inline int read()
    23. {
    24. 	int x=0,f=1;
    25. 	char c=getchar();
    26. 	while(c<'0'||c>'9')
    27. 	{
    28. 		if(c=='-') f=-1;
    29. 		c=getchar();
    30. 	}
    31. 	while(c>='0'&&c<='9')
    32. 	{
    33. 		x=(x<<3)+(x<<1)+(c^48);
    34. 		c=getchar();
    35. 	}
    36. 	return x*f;
    37. }
    38.  
    39. inline void write(int x)
    40. {
    41. 	if(x<0) putchar('-'),x=-x;
    42. 	if(x>9) write(x/10);
    43. 	putchar(x%10+'0');
    44. }
    45.  
    46. inline void add(int u,int v,int w)
    47. {
    48. 	edge[++num].to=v;
    49. 	edge[num].w=w;
    50. 	edge[num].next=head[u];
    51. 	head[u]=num;
    52. }
    53.  
    54. inline bool spfa()
    55. {
    56. 	memset(dis,INF,sizeof(dis));
    57. 	q.push(n+1); //从超级原点开始查找
    58. 	vis[n+1]=1;
    59. 	dis[n+1]=0; 
    60. 	while(!q.empty())
    61. 	{
    62. 		int u=q.front();
    63. 		q.pop();
    64. 		vis[u]=0;
    65. 		for(int i=head[u];i!=-1;i=edge[i].next)
    66. 		{
    67. 			int v=edge[i].to;
    68. 			if(dis[v]>dis[u]+edge[i].w)
    69. 			{
    70. 				dis[v]=dis[u]+edge[i].w;
    71. 				if(!vis[v])
    72. 				{
    73. 					q.push(v);
    74. 					vis[v]=1;
    75. 				}
    76. 			}
    77. 		}
    78. 	}
    79. 	return 0;
    80. }
    81.  
    82. int main()
    83. {
    84. 	n=read(); h=read();
    85. 	memset(head,-1,sizeof(head));
    86. 	for(int i=0;i<=n;++i)
    87. 	{
    88. 		add(n+1,i,0); //这里的超级原点是n+1 
    89. 	}
    90. 	
    91. 	for(int i=1;i<=h;++i)
    92. 	{
    93. 		edge1[i].b=read();
    94. 		edge1[i].e=read();
    95. 		edge1[i].t=read();
    96. 		add(edge1[i].e,edge1[i].b-1,-edge1[i].t); //建边方式
    97. 	}
    98. 	for(int i=1;i<=n;++i)
    99. 	{
    100. 		add(i,i-1,0);
    101. 		add(i-1,i,1);
    102. 	}
    103. 	spfa();
    104. 	write(-dis[0]); //输入的时候是负边权，输出要取反；
    105. 	return 0;
    106. }

  • 相关阅读:
    Spring MVC：文件的上传与下载
    DSSD : Deconvolutional Single Shot Detector
    腾讯云轻量应用服务器性能差吗？为什么便宜？
    【Java】文件操作 详解
    【Web项目实战】Cfeng.net基于MinIO的文件服务和支持markdown编辑的笔记服务
    语音分离---学习笔记（1）
    【蓝桥杯冲击国赛计划第5天】哈希表
    Python 学习 Day34
    程序媛的mac修炼手册-- 2024如何彻底卸载Python
    12-使用vue2实现todolist待办事项
  • 原文地址：https://blog.csdn.net/gzkeylucky/article/details/126084992