差分约束

作者: opbnbjs | 来源:发表于2018-06-02 21:49 被阅读16次

    差分约束

    什么是差分约束?

    差分约束系统(system of difference constraints),是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。
    (以上转自某博客)
    其实。。差分约束在某种程度上来说像是一个转换的工具,解释请看下文

    差分约束的核心思路

    差分约束大部分时候像是把一个问题转换为几个不等式,并转换为最短路来求解
    如何转换为最短路?
    我们用到了三角不等式。
    B - A <= c (1)

    C - B <= a (2)

    C - A <= b (3)

    如果要求C-A的最大值,可以知道max(C-A)= min(b,a+c)
    如:对于一个 xi-xj<=an
    则有一条i到j的边,权值为an。以此来建图。
    有些时候不等式不是现成的,这是需要对现有的不等式进行加减。如
    x3-x2<=1
    x2-x1<=3
    可以将两式相加,得到新的不等式
    (三角不等式也被经常用来做最短路的松弛操作)

    最长路&最短路

    最长路

    最长路就是第一个点到第n个点的最短路
    证明可以另查(实际上我也不会证)
    但是你可以这么理解
    对于一个式子a-b,当a一定,b越小,这个式子的值越大

    最短路

    最短路其实和最长路相反,是第一个点到第n个点的最长路
    证明方法同上理(就是b大了,a-b的值就小了)

    判断有没有解

    就是用spfa来判环
    (据说优化后的bellman-ford也可以)

    干货版(转自其他博客)

    上面的是我通俗化过的,但是如果你想看看最正式的解释也是可以的
    下面有一个超级源点,其实就是在处理特例
    差分约束系统的解法如下:

    1、 根据条件把题意通过变量组表达出来得到不等式组,注意要发掘出隐含的不等式,比如说前后两个变量之间隐含的不等式关系。

    2、 进行建图:

    首先根据题目的要求进行不等式组的标准化。

    (1)、如果要求取最小值,那么求出最长路,那么将不等式全部化成xi – xj >= k的形式,这样建立j->i的边,权值为k的边,如果不等式组中有xi – xj > k,因为一般题目都是对整形变量的约束,化为xi – xj >= k+1即可,如果xi – xj = k呢,那么可以变为如下两个:xi – xj >= k, xi – xj <= k,进一步变为xj – xi >= -k,建立两条边即可。

    (2)、如果求取的是最大值,那么求取最短路,将不等式全部化成xi – xj <= k的形式, 这样建立j->i的边,权值为k的边,如果像上面的两种情况,那么同样地标准化就行了。

    (3)、如果要判断差分约束系统是否存在解,一般都是判断环,选择求最短路或者最长路求解都行,只是不等式标准化时候不同,判环地话,用spfa即可,n个点中如果同一个点入队超过n次,那么即存在环。

    值得注意的一点是:建立的图可能不联通,我们只需要加入一个超级源点,比如说求取最长路时图不联通的话,我们只需要加入一个点S,对其他的每个点建立一条权值为0的边图就联通了,然后从S点开始进行spfa判环。最短路类似。

    3、 建好图之后直接spfa或bellman-ford求解,不能用dijstra算法,因为一般存在负边,注意初始化的问题。

    程序实现

    其实你可以去看看poj的1201-intervals。这道题被许多博客当做范例来讲,感觉也确实像是一个模版题。可以试试。
    附上不是我的标程一个(主要是poj最近打不开)

    #include<cstdio>  
    #include<cstring>  
    #include<queue>  
    #include<algorithm>  
    using namespace std;  
    const int maxn= 50000+10;  
    const int maxm=500000+10;  
    #define INF 1e9  
      
    struct Edge  
    {  
        int from,to,dist;  
        Edge(){}  
        Edge(int f,int t,int d):from(f),to(t),dist(d){}  
    };  
      
    struct SPFA  
    {  
        int n,m;  
        int head[maxn],next[maxm];  
        Edge edges[maxm];  
        int d[maxn];  
        bool inq[maxn];  
      
        void init()  
        {  
            m=0;  
            memset(head,-1,sizeof(head));  
        }  
      
        void AddEdge(int from,int to,int dist)  
        {  
            edges[m]=Edge(from,to,dist);  
            next[m]=head[from];  
            head[from]=m++;  
        }  
      
        int spfa()  
        {  
            memset(inq,0,sizeof(inq));  
            for(int i=0;i<n;i++) d[i]= i==0?0:INF;  
            queue<int> Q;  
            Q.push(0);  
      
            while(!Q.empty())  
            {  
                int u=Q.front(); Q.pop();  
                inq[u]=false;  
      
                for(int i=head[u];i!=-1;i=next[i])  
                {  
                    Edge &e=edges[i];  
                    if(d[e.to]>d[u]+e.dist)  
                    {  
                        d[e.to]=d[u]+e.dist;  
                        if(!inq[e.to])  
                        {  
                            inq[e.to]=true;  
                            Q.push(e.to);  
                        }  
                    }  
                }  
            }  
            return d[n-1]-d[9];  
        }  
    }SP;  
      
    int main()  
    {  
        int n,max_v=-1;  
        scanf("%d",&n);  
        SP.init();  
        while(n--)  
        {  
            int a,b,c;  
            scanf("%d%d%d",&a,&b,&c);  
            b+=10,a+=10;//所有值都加10了,以免a-1成为-1  
            max_v=max(max_v,b);  
            SP.AddEdge(b,a-1,-c);  
        }  
        for(int i=10;i<=max_v;i++)//从该循环可看出,本差分约束的点编号为:[9,max_v](未包含超级源0号点)  
        {  
            SP.AddEdge(i,i-1,0);  
            SP.AddEdge(i-1,i,1);  
            SP.AddEdge(0,i,0);  
        }  
        SP.AddEdge(0,9,0);  
        SP.n=max_v+1;  
        printf("%d\n",SP.spfa());//注意最终结果是d[max_v]-d[9]的值,而不是d[max_v]的单独值  
        return 0;  
    }
    

    思路还是一样的,只是感觉这个代码写的。。不是很通俗易懂

    差分约束就到这里了,我觉得它更像一个工具,有种数形结合百般好的感觉

    相关文章

      网友评论

        本文标题:差分约束

        本文链接:https://www.haomeiwen.com/subject/aehdsftx.html