Tag-差分约束系统

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-08-18 19:27:53 |  0 Comments  |  差分约束系统

CCPC 2017-2018 Finals HDU 6252 Subway Chasing 差分约束系统

题目大意

两个人从家里出发,Panda比Sheep晚走x分钟,在地铁上两人保持m次通信,每次通信Panda在a和b之间,Sheep在c和d之间。到终点后,求问每两站之间所需要的时间是多少,如果无法计算输出IMPOSSIBLE

题解

我们可以在草稿纸上画画图,把两人的位置之间连线,标记上表示这一段的时间为x。

然后我们可以看到两者区间两端点的关系,进行分类讨论:

如果a = b:

1.c = d 那么就是c - a = x,也就是c - a <= x, c - a >= x,也即 c - a  <= x,a - c <= -x;

2.c ≠ d 则c - a < x,d - a > x,也即c - a  <= x-1,a - d <= -x-1;

如果a ≠ b:

1. c = d 那么就是 c - a > x,c - b < x,也即a - c <= -x-1,c - b <= x-1;

2. c ≠ d 那么就是c - b < x,d - a > x,也即c - b <= x - 1,a - d <= -x-1;

根据这些关系很容易就能想到此题是一个差分约束系统。只需要用SPFA求解就行了。

IMPOSSIBLE的情况就是出现负环或者正环(看自己怎么定义边了,要注意SPFA中的更新的不等号方向要和建边一致,不然会WA)。

非IMPOSSIBLE的情况,两站之间的距离就是dis[i] - dis[i-1](标程里面写的是最长路,所以也就是非正环情况)。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 2005;
typedef long long ll;
struct edge{
    int to,next;
    ll dis;
}e[maxn<<5];
int cnt = 0;
int t;
int h[maxn];
int a,b,c,d;
int n,m;
ll x;
void add(int u,int v,int d){
    e[cnt].to = v;e[cnt].next = h
 2019-02-13 09:33:40 |  0 Comments  |  最短路 差分约束系统

[转载]差分约束系统详细讲解

差分约束系统

一、何为差分约束系统:
差分约束系统(system of difference constraints),是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。
通俗一点地说,差分约束系统就是一些不等式的组,而我们的目标是通过给定的约束不等式组求出最大值或者最小值或者差分约束系统是否有解。
比如:


二、差分约束系统的求解:
差分约束系统可以转化为图论来解决,对应于上面的不等式组,如果要求出x3-x0的最大值的话,叠加不等式可以推导出x3-x0<=7,最大值即为7,我们可以通过建立一个图,包含6个顶点,对每个xj-xi<=bk,建立一条i到j的有向边,权值为bk。通过求出这个图的x0到x3的最短路可以知道也为7,这是巧合吗?并不是。
之所以差分约束系统可以通过图论的最短路来解,是因为xj-xi<=bk,会发现它类似最短路中的三角不等式d[v] <=d[u]+w[u,v],即d[v]-d[u]<=w[u,v]。而求取最大值的过程类似于最短路算法中的松弛过程。
三角不等式:(在此引用大牛的博客)
B - A <= c     (1)
C - B <= a     (2)
C - A <= b     (3)
 如果要求C-A的最大值,可以知道max(C-A)= min(b,a+c),而这正对应了下图中C到A的最短路。


因此,对三角不等式加以推广,变量n个,不等式m个,要求xn-x1的最大值,便就是求取建图后的最短路。
同样地,如果要求取差分约束系统中xn-x1的最小值,便是求取建图后的最长路。最长路可以通过spfa求出来,只需要改下松弛的方向即可,即if(d[v] < d[u] + dist(u,v)) d[v] = d[u] + dist(u,v)。当然我们可以把图中所有的边权取负,求取最短路,两者是等价的。
最长路求解算法证明如下:
http://www.cnblogs.com/g0feng/archive/2012/09/13/2683880.html
最后一点,建图后不一定存在最短路/最长路,因为可能存在无限减小/增大的负环/正环,题

Title - Artist
0:00