差分约束学习笔记

这篇具有很好参考价值的文章主要介绍了差分约束学习笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

2023.5.6 写的太烂了重新写

差分约束系统

定义

差分约束系统是一种特殊的 \(n\) 元一次不等式组,它包含 \(n\) 个变量 \(x_{1},x_{2},...,x_{n}\) 以及 \(m\) 个约束条件,每一个约束条件都是两个其中的变量做差构成的,形如 \(x_{i}-x_{j}\le c_{k}\),其中 \(1\le i,j\le n,i\ne j,1\le k\le m\) 并且 \(c_{k}\) 是常数(可以为正数或非正数)。
------- OI Wiki

通俗一点讲,这类问题都是给定 \(n\) 个变量,\(m\) 个限制,类似于:

\[\left\{\begin{matrix} op_{1}:x_{1}-x_{2}=c_{1}\\ op_{2}:x_{4}-x_{n}=c_{2}\\ ......\\ op_{m}:x_{n}-x_{3}=c_{m} \end{matrix}\right. \]

有了这些条件,一般的题目会让你求出一组合法的解,也就是求这 \(n\) 个变量的合法的值。

过程

我们可以建一个超级源点,然后向每一个点连一条边权为 \(0\) 的边,然后跑单源最短路;而上面的 \(m\) 个限制都可以变形为 \(x_{i}\le x_{j}+c_{k}\),这个东西很容易想到我们在跑最短路的时候的松弛操作里的 \(dis[v]\le dis[u]+w\),因此我们就可以把每一个变量看作是一个图中的点,对于每一个条件 \(x_{i}-x_{j}\le c_{k}\),从 \(j\)\(i\) 连一条边权为 \(c_{k}\) 的有向边。

我们在求解的时候一般用 SPFA 来跑,虽然他最坏的时间复杂度是 \(O(nm)\) 的,但是我们的差分约束里面要是有负环的话,就说明是无解,再加上有负边权,SPFA 这个已死的算法成了最好的方法,更何况他在一些随机的图中跑的飞快。

最后一个问题,最后转化的式子是 \(x_{i}\le x_{j}+c_{k}\),为什么跑最短路?

但是我觉得,当你建图的时候使用的是 \(x_{i}-x_{j}\le c_{k}\) 形式的方程组建图时,即 \(j\)\(i\) 连一条权值为 \(c_{k}\) 的边,应该选择跑最短路。

如果使用的是 \(x_{i}-s_{j}\ge c_{k}\) 形式的方程组来建图时,应该选择跑最长路。

P5960 【模板】差分约束算法

code:文章来源地址https://www.toymoban.com/news/detail-435235.html

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 50100
using namespace std;
int n,m,cnt,head[N];
queue<int>q;
struct SB{int w,v,next;}e[N<<1];
int dis[N],tot[N],vis[N];
inline void add(int u,int v,int w)
{
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int SPFA()
{
	
	q.push(0);
	vis[0]=1;
	tot[0]++;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push(v);
				vis[v]=1;
				tot[v]++;
				if(tot[v]==n+1)
				return 0;
			}
		}
	}
	return 1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	  dis[i]=INF;
	for(int i=1;i<=n;i++)
	  add(0,i,0);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(y,x,z);
	}
	if(!SPFA())
	  cout<<"NO"<<endl;
	else
	  for(int i=1;i<=n;i++)
		cout<<dis[i]<<" ";
	return 0;
}

到了这里,关于差分约束学习笔记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【OI学习笔记】基础算法-前缀和与差分算法

    板块:基础算法、线性优化 难度:较易 前置知识:C++基础语法 在一维空间中,对于一个数据总量为 n n n 的数组 a a a ,有数据 a [ 1 ] , a [ 2 ] , a [ 3 ] , . . . , a [ n − 1 ] , a [ n ] a[1],a[2],a[3],...,a[n-1],a[n] a [ 1 ] , a [ 2 ] , a [ 3 ] , ... , a [ n − 1 ] , a [ n ] ,定义一个数组 s u m sum s u m ,

    2024年02月08日
    浏览(48)
  • MySql学习笔记06——约束介绍

    约束对应的英语单词:constraint 在创建表的时候,我们可以给表中的字段加上一些约束,来保证这个表中数据的完整性、有效性!!!约束的作用就是为了保证:表中的数据有效!! 非空约束 not null 唯一性约束 unique 主键约束 primary key 外键约束 foreign key 检查约束 check (mys

    2024年02月09日
    浏览(35)
  • 《横向联邦学习中 PCA差分隐私数据发布算法》论文算法原理笔记

    论文地址:https://www.arocmag.com/article/01-2022-01-041.html 论文摘要      为了让不同组织在保护本地敏感数据和降维后发布数据隐私的前提下,联合使用 PCA进行降维和数据发布,提出 横向联邦 PCA差分隐私数据发布算法 。引入随机种子联合协商方案,在各站点之间以较少通信代

    2024年02月08日
    浏览(37)
  • 算法基础学习笔记——④前缀和\差分\双指针\位运算

    ✨ 博主: 命运之光 ✨ 专栏: 算法基础学习 目录 ✨前缀和 ✨一维前缀和 🍓一维前缀和模板: ✨二维前缀和 🍓二位前缀和模板: 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,感谢大家的支持! 原i:a[1] a[2] a[3] …a[n] 前缀和:s[i]=a[1]+a[2]+…+a[i] s[0]=0(方便处理

    2024年02月08日
    浏览(46)
  • 机器学习笔记之优化算法(一)无约束优化概述

    从本节开始,将介绍 优化算法 ( Optimization Algorithm ) (text{Optimization Algorithm}) ( Optimization Algorithm ) 。 基于支持向量机 ( Support Vector Machine,SVM ) (text{Support Vector Machine,SVM}) ( Support Vector Machine,SVM ) 最大间隔分类器 的朴素思想: 从能够将所有样本点 正确分类 的直线中找到 满足

    2024年02月15日
    浏览(43)
  • 【深度学习】卷积神经网络(LeNet)【文章重新修改中】预计2023年11月修改完成

    全连接神经网络,也称多层感知机, M L P MLP M L P ,是深度学习最基本的神经网络之一。它包含输入层,多个隐藏层和输出层,每一层都与前一层的每个神经元相连接。尽管全连接神经网络具有一定的表达能力,其并不是解决所有问题的最佳工具。 e . g . e.g. e . g . 假设我们有

    2024年02月07日
    浏览(38)
  • 机器学习笔记之最优化理论与方法(九)无约束优化问题——常用求解方法(下)

    上一节介绍了 牛顿法、拟牛顿法 。本节将继续以 拟牛顿法 为基础,介绍 DFP , BFGS text{DFP},text{BFGS} DFP , BFGS 方法 。 经典牛顿法缺陷与修正牛顿法 关于 经典牛顿法 中关于 下降方向 D k ( k = 1 , 2 , ⋯   , ∞ ) mathcal D_k(k=1,2,cdots,infty) D k ​ ( k = 1 , 2 , ⋯ , ∞ ) 的 数学符号 表

    2024年02月09日
    浏览(51)
  • 机器学习笔记之最优化理论与方法(七)无约束优化问题——常用求解方法(上)

    本节将介绍 无约束优化问题 的常用求解方法,包括 坐标轴交替下降法、最速下降法 。 本节是对优化算法(十~十七)最速下降法(梯度下降法)的理论补充,其中可能出现一些定理的 证明过程 这里不再赘述,并在相应位置 附加链接 。 从本节开始,将介绍 四大类 无约束优化问

    2024年02月10日
    浏览(49)
  • 机器学习笔记之最优化理论与方法(十)无约束优化问题——共轭梯度法背景介绍

    本节将介绍 共轭梯度法 ,并重点介绍共轭方向法的逻辑与几何意义。 关于 最小化 二次目标函数: min ⁡ f ( x ) = min ⁡ 1 2 x T Q x + C T x begin{aligned}min f(x) = min frac{1}{2} x^T mathcal Q x + mathcal C^T xend{aligned} min f ( x ) = min 2 1 ​ x T Q x + C T x ​ ,其中 Q ∈ R n × n ; Q ≻ 0 mathcal Q

    2024年02月09日
    浏览(46)
  • 记录--你的代码不堪一击!太烂了!

    小王,你的页面白屏了,赶快修复一下。小王排查后发现是服务端传回来的数据格式不对导致,无数据时传回来不是 [] 而是 null , 从而导致 forEach 方法报错导致白屏,于是告诉测试,这是服务端的错误导致,要让服务端来修改,结果测试来了一句:“服务端返回数据格式错误

    2024年02月16日
    浏览(24)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包