首页 > 其他分享 >差分约束

差分约束

时间：2023-10-14 13:45:40浏览次数：42  
标签：head le int 差分 约束 vis dis

差分约束

前言

又是 20231012联考 T4 考到。。。

于是不会，前面的题也没有补，开始学习！

定义

差分约束是什么，看起来和图论没有一点关系。。。

差分约束系统是一种特殊的 \(n\) 元一次不等式组，\(n\) 个变量 \(x_1,x_2,\dots ,x_n\)，和 \(m\) 个约束条件，

每个条件都是形如 \(x_i-x_j \le c_k\)，让你求一组解。

发现把这个式子变形一下就是 \(x_i \le x_j +c_k\)，

这个东西和单源最短路中的 \(dis[v] \le dis[u]+w\) 非常相似。

于是我们考虑把 \(x_i\) 看作一个节点，从 \(x_j\) 到 \(x_i\) 建一条长度为 \(c_k\) 的有向边。

好妙哦

过程

建出图之后，我们再建立一个源点 \(dis[0]=0\)，

向每一个点链接一条长度为 \(0\) 的边，跑单元最短路，

如果图中存在负环，于是差分约束无解，

否则，\(x_i=dis[i]\) 就是一组解。

例题

先来考虑如何判负环——

P3385 【模板】负环

传送门

负环就是在用 spfa 跑的过程中，如果入队次数超过了 \(n\) ，那就一定存在负环。

时间复杂度有可能被卡到 \(O(nm)\)。

#include <bits/stdc++.h>
using namespace std;

const int N=1e4+5;
int T,n,m,head[N],tot=0,cnt[N],dis[N];
struct edge{
  int v,nxt,w;
}e[N<<1];
bool vis[N];

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void add(int u,int v,int w){
  e[++tot]=(edge){v,head[u],w};
  head[u]=tot;
}

void spfa(){
  memset(dis,0x3f,sizeof(dis));
  memset(vis,false,sizeof(vis));
  dis[1]=0;vis[1]=true;
  queue<int> q;q.push(1);
  while(!q.empty()){
  	int u=q.front();q.pop();
  	vis[u]=false;
  	for(int i=head[u];i;i=e[i].nxt){
  	  int v=e[i].v,w=e[i].w;
	  if(dis[v]>dis[u]+w){
	  	dis[v]=dis[u]+w;
	  	if(!vis[v]){
	  	  if(++cnt[v]>=n){puts("YES");return;}
		  q.push(v);vis[v]=true;
		}
	  }	
	}
  }
  puts("NO");
}

int main(){
  /*2023.10.13 H_W_Y P3385 【模板】负环 spfa*/
  T=read();
  while(T--){
  	n=read();m=read();
  	memset(head,0,sizeof(head));tot=0;
  	memset(cnt,0,sizeof(cnt));
  	for(int i=1,u,v,w;i<=m;i++){
  	  u=read();v=read();w=read();
	  add(u,v,w);
	  if(w>=0) add(v,u,w);	
	}
	spfa();
  }
  return 0;
}

P5590 赛车游戏

有些时候一定不要忘记打标记！

传送门

你发现边权的范围是 \([1,9]\) ，那么在有解的情况下，

对于有向边 \((u,v)\)，需要满足：

\[1 \le d[v]-d[u] \le 9 \]

于是我们把式子转化一下，就变成了：

\[d[v] \le d[u]+9\\ d[u] \le d[v]+(-1) \]

我们就可以用差分约束做了。

具体就是先用 dfs 找出在 \(1 \sim n\) 路径上面的边，（dfs 需要简单优化，就是走过不再走）

建出一个新图，再跑 spfa 判负环即可。

最后输出就是通过判断 \(d[v]-d[u]\) 的大小来确定边权。

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,head[N],tot=0,dis[N],m,cnt[N],h[N],t=0;
struct edge{
  int v,nxt,w;
}e[N<<1],E[N<<1];
struct node{
  int u,v;
}a[N<<1];
bool vis[N],pp[N];

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void print(int x,char s){
  int p[15],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x){
  	p[++tmp]=x%10;
  	x/=10;
  }
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
  putchar(s);
}

void add(int u,int v,int w){
  e[++tot]=(edge){v,head[u],w};
  head[u]=tot;
}

void add2(int u,int v){
  E[++t]=(edge){v,h[u]};
  h[u]=t;
}

bool spfa(){
  memset(dis,0x3f,sizeof(dis));
  memset(vis,false,sizeof(vis));
  dis[1]=0;vis[1]=true;
  queue<int>q;q.push(1);
  while(!q.empty()){
  	int u=q.front();q.pop();
  	vis[u]=false;
  	for(int i=head[u];i;i=e[i].nxt){
  	  int v=e[i].v,w=e[i].w;
	  if(dis[v]>dis[u]+w){
	  	dis[v]=dis[u]+w;
	  	if(!vis[v]){
	  	  if(++cnt[v]>n) return true;
		  q.push(v),vis[v]=true;	
		}
	  }	
	}
  }
  return false;
}

bool dfs(int u){
  if(u==n||pp[u]) return true;
  for(int i=h[u];i;i=E[i].nxt){
  	int v=E[i].v;
	if(!vis[i]){
  	  vis[i]=true;
  	  if(dfs(v)){
  	    pp[u]=true;
		add(u,v,9);add(v,u,-1);	
	  }	
	}  	
  }

  return pp[u];
}

int main(){
  /*2023.10.13 H_W_Y P5590 赛车游戏 差分约束*/ 
  n=read();m=read();
  for(int i=1,u,v;i<=m;i++) u=read(),v=read(),add2(u,v),a[i]=(node){u,v};
  if(!dfs(1)||spfa()){puts("-1");return 0;}
  print(n,' ');print(m,'\n');
  for(int i=1;i<=m;i++){
  	int ans=dis[a[i].v]-dis[a[i].u];
  	print(a[i].u,' ');print(a[i].v,' ');
  	if(ans>=1&&ans<=9) print(ans,'\n');
  	else puts("1");
  }
  return 0;
}

ARC177F-Gateau

传送门

现在回到那联考题。

我们通过前缀和+二分分析了以下内容。

现在我们考虑一个答案 \(x\) ，我们想验证它是否合法。

由于题目中是求每 \(n\) 个数的和，

所以我们设 \(s_i\) 为前缀和数组，且序列编号从 \(0\) 开始，于是 \(s_0=0\)，则：

\[0 \le i \lt n \to s_{i+n}-s_i\ge a_i\\ n \le i \lt 2n \to s_i-s_{i-n} \le x-a_i \]

于是发现其实 \(s_{i+n}-s_i\) 和 \(s_i-s_{i-n}\) 是一个东西，

所以就有了一个对于 \(s_{i+n}-s_i\) 的上界和下界：

\[l_i=a_i,r_i=x-a_{i+n}\\ li \le s_{i+n}-s_i\le r_i \]

现在考虑如何构造，

由于 \(s_i \ge s_{i-1}\) ，所以我们可以依次枚举过来，进行贪心：

  1. 若 \(l_i \le s_{i+n-1}-s_{i-1} \le r_i\) ，说明前面已经满足条件，则 \(s_i=s_{i-1},s_{i+n}=s_{i+n-1}\)。
  2. 若 \(s_{i+n-1}-s_{i-1}\lt l_i\)，则 \(s_i=s_{i-1},s_{i+n}=s_{i-1}+l_i\)，这样可以保证 \(s_{i+n}\gt s_{i+n-1}\)
  3. 若 \(s_{i+n-1}-s_{i-1}\gt r_i\)，则 \(s_i=s_{i+n-1}-r_i,s_{i+n}=s_{i+n-1}\)。

发现这样枚举只用算前面 \(n\) 个，那怎么知道是满足条件呢？

很容易想到，最后的 \(s_i\) 需要满足：

\[s_{n-1} \le s_n ,s_{2n-1} \le x \]

你发现 \(s_n-s_{n-1}\) 和 \(s_{2n-1}\) 一定是随 \(x\) 增加而增加，

因为在 \(x\) 增加的过程中，相当于每次把上限扩大了。

于是就可以用二分解决。

于是就得到了一个双重二分的方法，外层枚举 \(x\) ，内层二分 \(s_0\) 和 \(s_n\) 的大小即可。

时间复杂度 \(O(n \log^2 v)\)

现在发现 \(l_i \le s_{i+n}-s_i \le r_i\) 这个式子非常像差分约束，

于是我们就可以用差分约束来做一做。

下标从 \(1\) 开始，注意每次在最后还要保证：

\[x \le s_{2n}-s_0 \le x \]

#include <bits/stdc++.h>
using namespace std;

const int N=3e5+5;
int n,c[N],head[N],tot=0,dis[N],cnt[N],l,r,dep[N];
bool vis[N];
struct edge{
  int v,nxt,w;
}e[N<<1];

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void add(int u,int v,int w){
  e[++tot]=(edge){v,head[u],w};
  head[u]=tot;
}

bool spfa(){
  memset(vis,false,sizeof(vis));
  memset(dis,0x3f,sizeof(dis));
  memset(dep,0,sizeof(dep));
  dis[0]=0;vis[0]=true;
  queue<int> q;q.push(0);
  while(!q.empty()){
    int u=q.front();q.pop();
    vis[u]=false;
    for(int i=head[u];i;i=e[i].nxt){
      int v=e[i].v,w=e[i].w;
      if(dis[v]>dis[u]+w){
      	dis[v]=dis[u]+w;
      	dep[v]=dep[u]+1;
      	if(dep[v]>(n<<1)) return false;
      	if(!vis[v]){
		  q.push(v);vis[v]=true;	
		  if(dis[q.back()]<dis[q.front()]) swap(q.front(),q.back());
		}
	  }
	}
  }
  return true;
}

bool chk(int x){
  int L,R;
  for(int i=0;i<=(n<<1);i++) head[i]=cnt[i]=0;tot=0;
  for(int i=1;i<=n;i++){
  	L=c[i];R=x-c[i+n];
  	if(L>R) return false;
  	add(i,i+n,R);add(i+n,i,-L);
  }
  for(int i=1;i<=(n<<1);i++) add(i,i-1,0);
  add(0,(n<<1),x);add((n<<1),0,-x);
  return spfa();
}

int main(){
  n=read();
  for(int i=1;i<=(n<<1);i++) c[i]=read(),r=max(r,c[i]);
  l=0;r<<=1;
  while(l<r){
  	int mid=(l+r)/2;
  	if(chk(mid)) r=mid;
  	else l=mid+1;
  }
  printf("%d\n",l);
  return 0;
}

现在考虑如何优化？

发现我们判负环跑 \(spfa\) 的时间太长了，

于是我们考虑高级的操作——人脑判负环！

把这张图画出来，发现特别特殊，

现在我们考虑把这个图进行分层，于是就变成了这样：

image

发现只有两条红色的边会构成环，

于是负环上面要么包含 \(0\) ，要么包含 \(s_{n+1} \to s_{n}\)，

于是我们把红边删掉，

从 \(0\) 开始跑最短路，再从 \(n\) 开始跑最短路，判断最后的距离是否非负即可。

如果最短路是负数——那么一定存在负环。

用 \(dp\) 可以做到线性。

时间复杂度 \(O(n \log v)\)，别忘了开 long long！！！

#include <bits/stdc++.h>
using namespace std;
#define ll long long 

const int N=5e5+5;
const ll inf=1e18;
int n,c[N],l,r;
ll dis[N];

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void wrk(int x){
  for(int i=2*n-1;i>n;i--){
  	dis[i]=min(dis[i+1],dis[i-n+1]+x-c[i+1]);
  	dis[i-n]=min(dis[i-n+1],dis[i]-c[i-n+1]);
  }
}

void init(){for(int i=0;i<=(n<<1);i++) dis[i]=inf;}

bool chk(int x){
  init();dis[0]=0;dis[(n<<1)]=x;wrk(x);//从 0 出发跑 
  if(dis[1]<0||dis[n+1]-c[1]<0||dis[(n<<1)]-c[1]-c[n+1]<0) return false;
  init();dis[n]=0;wrk(x);//从 n 出发，先把前面的点更新了 
  dis[0]=min(dis[0],dis[1]);dis[(n<<1)]=min(dis[(n<<1)],dis[0]+x);//处理 n~2n 里面的初值 
  wrk(x);//更新 n ~ 2n 从 n 出发的值 
  if(dis[0]+x-c[n+1]<0||dis[n+1]<0||dis[(n<<1)]-c[n+1]<0) return false;
  init();dis[(n<<1)]=0;wrk(x);//从 2n 开始跑
  dis[0]=min(dis[0],dis[1]);
  if(dis[0]+x-c[(n<<1)+1]+x-c[n+1]<0||dis[n+1]+x-c[(n<<1)+1]<0) return false;
  return true; 
}

int main(){
  n=read();
  for(int i=1;i<=(n<<1);i++) c[i]=read(),r=max(r,c[i]);
  for(int i=1;i<=n;i++) l=max(l,c[i]+c[i+n]);
  c[(n<<1)+1]=c[1];r<<=1;
  while(l<r){
  	int mid=(l+r)/2;
  	if(chk(mid)) r=mid;
  	else l=mid+1;
  }
  printf("%d\n",l);
  return 0;
}

Conclusion

差分约束时间复杂度过大时可以考虑人脑判负环。

标签：head,le,int,差分,约束,vis,dis
From： https://www.cnblogs.com/hwy0622/p/17764079.html

相关文章

  • Day2 前缀和 差分 双指针
    前缀和LuoguP2004领地选择二维前缀和板题，注意开longlong#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;intn,m,c,x,y;longlongans,a[1005][1005],s[1005][1005];intmain(){ scanf("%d%d%d",&n......
  • 6577: 暗的连锁 LCA+树上差分
    描述  Dark是一张无向图，图中有N个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark有N–1条主要边，并且Dark的任意两个节点之间都存在一条只由主要边构成的路径。另外，Dark还有M条附加边。你的任务是把Dark斩为不连通的两部分。一开始Dark的附加边......
  • 如何解决逻辑删除is_del与数据库唯一约束冲突
    前言不知道大家有没有遇到这么一种业务场景，在业务中有个唯一约束A，当该业务进行逻辑删除后（设置标记为删除状态is_del=1），再往唯一约束列插入相同的值时，此时会报Duplicateentry，但在业务上，该值时必须要插入的。今天我们就来聊聊处理这种业务场景的几种思路解决思路方案一：不采用逻......
  • Conveyor (CF E) (dp 差分/前缀 条件迷惑t)
     思路: 找各种性质1每一秒只有史莱姆进入起始点,然后他会选一个方向走(右或者下),每一秒史莱姆都会这样走在考虑前t秒内有S个史莱姆到达这个点,然后就会有s+1/2个往右走,s/2往下走而且问t秒只会有t-n-m-1秒后的时刻影响(诈骗t)于是利用dp+差......
  • P5960 差分约束
    原题曾经会过对于\(x_i-x_j\leqk\)，我们发现长得很像最短路/最长路的形式，因此我们可以抽象建图建一个超级源点连向所有点，从超级原点跑最短路算法，跑出来的\(dis_i\)即对应\(x_i\)的一个解前文提到过，差分约束问题可以转化为最短路或最长路问题，所以两种转化也就形成了两......
  • 3D：约束：斜线打平2
    1.编辑几何体——约束——无改为边2.选中斜线，拉到相邻直边上即变直3.绝对坐标改为相对，Y轴偏移20即可......
  • 二阶差分——进行一个等差数列的加
    一般的差分用于对一段区间进行加减，但如果在该区间内加减的是一段等差数列呢？对于一段区间[l,r],加一段首项为s,末项为e的等差数列。其公差d=(s-e)/(r-l+1)为简化问题讨论，先假设这段区间都为0。原数组：0000000添加后的数组：0046800第一次差分：00422-8......
  • 约束
    ==约束==约束包括哪些？非空约束：notnull唯一性约束:union约束的字段不可以重复，但是可以为null主键约束:primarykey外键约束:foreignkey检查约束：check（MySql不支持）两个字段联合唯一：--这样就相当于把两列的数据看成了一列，只有当两列数据都相同的时候才会触发唯一性约束......
  • PostgreSQL教程：约束（主键、非空、唯一、检查约束）
    核心在于构建表时，要指定上一些约束。约束主键--主键约束droptabletest;createtabletest(idbigserialprimarykey,namevarchar(32));非空--非空约束droptabletest;createtabletest(idbigserialprimarykey,namevarchar(32)notnull);......
  • 基本差分算法：一维差分、二维差分
    1、一维差分首先要知道，差分是前缀和的逆运算，a1a2……an前缀和b1b2……bn差分以AcWing.797为例，题目要求如下：输入一个长度为n的整数序列。接下来输入m个操作，每个操作包含三个整数l,r,c，表示将序列中[l,r]之间的每个数加上c。请你输出进行完所有操作后的序......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99