差分约束系统学习笔记

发布于 2018-03-17  421 次阅读


差分约束系统,就是给定一些 $ x_i - x_j >= d $ 的不等式,求出其中的一组解。我们可以转化为最短路来解决该类问题。

实现

PS:以下讨论整数情况,浮点数请注意精度。
我们对于每一组 $ x_i - x_j >= d $ 的不等式,从$ j $ 向 $ i $ 连一条长度为d的边。
可能有人会问:如果是其他状态的不等式呢?
我们可以利用以下转换:
1、 $ x_i - x_j >= dist $ 可以转换为 $ x_j - x_i <= -dist $
2、 $ x_i - x_j < dist $ 可以转换为 $ x_i - x_j <= dist - 1 $
3、 $ x_i - x_j == dist$ 可以转换为 $ x_i - x_j <= dist and x_j - x_i <= dist $

跑完后每个结点的dist及为结果。
一般在计算$ x_1 - x_n $最大解时跑最短路,最小解时跑最长路。
如果图中有负环,则无解。

例题

CodeVS4416
给出n个形如 $ x_i - x_j <= d $ 或 $ x_i - x_j >= d $ 的不等式,求一组$ x_1 - x_n $最大的解。
如果无解输出-1,差无限大输出-2。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <climits>

const int MAXN = 1000 + 5;

int N,M,K;

struct Node{
    int dist;
    int count;
    bool inQueue;
    struct Edge{
        Node *s,*t;
        int w;
        Edge *next;

        Edge(Node *s,Node *t,int w) : s(s), t(t), w(w), next(s->firstEdge) {}
    };
    Edge *firstEdge;
}node[MAXN];

inline void add(int u,int v,int w){
    node[u].firstEdge = new Node::Edge(&node[u],&node[v],w);
}

inline bool spfa(){
    for(int i = 1;i <= N;i++){
        node[i].dist = INT_MAX;
        node[i].inQueue = false;
    }
    std::queue<Node *> q;
    node[1].dist = 0;
    node[1].inQueue = true;
    q.push(&node[1]);
    while(!q.empty()){
        Node *v = q.front();q.pop();
        v->inQueue = false;
        for(Node::Edge *e = v->firstEdge;e;e = e->next){
            if(e->t->dist > v->dist + e->w){
                e->t->dist = v->dist + e->w;
                if(!e->t->inQueue){
                    q.push(e->t);
                    e->t->inQueue = true;
                    e->t->count++;
                    if(e->t->count > N) return false;
                }
            }
        }
    }
    return true;
}

int main(){
    scanf("%d%d%d",&N,&M,&K);
    for(int u,v,w,i = 1;i <= M;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    for(int u,v,w,i = 1;i <= K;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(v,u,-w);
    }
    if(!spfa())
        printf("%d",-1);
    else{
        if(node[N].dist == INT_MAX)
            printf("%d",-2);
        else
            printf("%d",node[N].dist);
    }
    return 0;
}

一个OIer。