如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如$x_j-x_i \le b_k$ $(i,j \in [1,n],k \in [1,m])$,则称其为差分约束系统(system of difference constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。

求解差分约束系统,可以转化成图论的单源最短路径(或最长路径)问题。

观察$x_j-x_i \le b_k$,会发现它类似最短路中的三角不等式 $d[v] \le d[u]+w[u,v]$,即$d[v]-d[u] \le w[u,v]$。因此,以每个变量$x_i$为结点,对于约束条件$x_j-x_i<=b_k$,连接一条边$(i,j)$,边权为$b_k$。我们再增加一个源点s,s与所有定点相连,边权均为0。对这个图,以s为源点运行Bellman-ford算法(或SPFA算法),最终${d[i]}$即为一组可行解。

POJ 3169 Layout

题目地址:http://poj.org/problem?id=3169

题目描述

Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1..N standing along a straight line waiting for feed. The cows are standing in the same order as they are numbered, and since they can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate).

Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.

Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.

思路

题中给出ML个关系好的牛(AL,BL,DL)以及MD个关系不好的牛(AD,BD,DD),这里表示的是牛AL和BL之间的最大距离为DL,牛AD与牛BD之间最小距离为DD。求1号牛与N号牛的最大距离。

记$i$号牛的位置为$d[i]$,首先牛是按照顺序排的,隐含条件$d[i+1] \ge d[i]$,为此可得一条边$$,权值为0。

关系好的牛条件$d[BL] - d[AL] \le DL$,为此可得一条边$w = DL$。

关系不好的牛条件$d[BD] - d[AD] \ge DD$,为此可得一条边$w = -DD$。

求出1到N的最短路即最大距离。由于有负边,考虑Bellman_Ford算法。

AC代码

/*************************************************************************
    > File Name: 3169.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-08-18 二 16:07:06 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

// 差分约束系统, 隐含条件: d[i] <= d[i+1]
int N, ML, MD;
const int INF = 0x3f3f3f3f;
int d[1005];
struct edge {
    int u, v, cost;
} es[21005];

bool Bellman(int s) {
    memset(d, 0x3f, sizeof(d));
    int L = ML + MD + N;
    d[s] = 0;
    for(int i=1; i<=N-1; ++i)
        for(int j=0; j<L; ++j) {
            edge & e = es[j];
            if(d[e.v] > d[e.u] + e.cost)
                d[e.v] = d[e.u] + e.cost;
        }

    for(int j=0; j<L; ++j)
        if(d[es[j].v] > d[es[j].u] + es[j].cost) {
            return false;
        }
    return true;
}

void solve() {
    cin.sync_with_stdio(false);
    cin >> N >> ML >> MD;
    for(int i=0; i<ML; ++i)
        cin >> es[i].u >> es[i].v >> es[i].cost;
    for(int i=0; i<MD; ++i) {
        cin >> es[i+ML].v >> es[i+ML].u >> es[i+ML].cost;
        es[i+ML].cost = -es[i+ML].cost;
    }
    for(int i=2; i<=N; ++i) {
        es[i+ML+MD].v = i-1; // 隐含条件,w<i+1, i> = 0;
        es[i+ML+MD].u = i;
        es[i+ML+MD].cost = 0;
    }

    if(Bellman(1)) {
        if(d[N] == INF)
            cout << -2 << endl;
        else
            cout << d[N] << endl;
    }
    else
        cout << -1 << endl;

}

int main()
{
#ifdef Oj
    freopen("3169.in", "r", stdin);
#endif
    solve();
    return 0;
}

POJ 1364 King

题目地址:http://poj.org/problem?id=1364

题目描述

现在假设有一个这样的序列,S={a1,a2,a3,a4…ai…at}

其中ai=a*si,其实这句可以忽略不看

现在给出一个不等式,使得$ai+a(i+1)+a(i+2)+...+a(i+n)ki$

首先给出两个数分别代表S序列有多少个数,有多少个不等式

不等式可以这样描述

给出四个参数第一个数i可以代表序列的第几项,然后给出n,这样前面两个数就可以描述为ai+a(i+1)+…a(i+n),即从i到n的连续和,再给出一个符号和一个ki

当符号为gt代表>,符号为lt代表<

那么样例可以表示

1 2 gt 0
a1+a2+a3>0
2 2 lt 2
a2+a3+a4<2

最后问你所有不等式是否都满足条件,若满足输出lamentable kingdom,不满足输出successful conspiracy,这里要注意了,不要搞反了

思路

设$S_n$为${a_n}$的前n项和。则

$$ w = -(c+1)\\ w = (c-1)$$

在利用Bellman_Ford判断,有负圈则无解。

AC代码

/*************************************************************************
    > File Name: 1364.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-08-19 三 14:35:05 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

struct edge{
    int u, v, cost;
} es[102];
int n, m;
int d[102];
bool Bellman_Ford(int s) {
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    for(int i=0; i<n; ++i)
        for(int j=0; j<m; ++j) {
            edge &e = es[j];
            d[e.v] = min(d[e.v], d[e.u] + e.cost);
        }
    for(int j=0; j<m; ++j) {
        edge &e = es[j];
        if(d[e.v] > d[e.u] + e.cost)
            return false;
    }
    return true;
}


void solve() {
    cin.sync_with_stdio(false);
    string op;
    int a,b,c;
    while(cin >> n && n) {
        cin >> m;
        for(int i=0; i<m; ++i) {
            cin >> a >> b >> op >> c;
            if(op == "gt") {
                es[i].u = a+b;
                es[i].v = a-1;
                es[i].cost = -(c+1);
            }
            else {
                es[i].u = a-1;
                es[i].v = a+b;
                es[i].cost = c-1;
            }
        }
        if(Bellman_Ford(0))
            cout << "lamentable kingdom" << endl;
        else
            cout << "successful conspiracy" << endl;

    }

}

int main()
{
#ifdef Oj
    freopen("1364.in", "r", stdin);
#endif
    solve();
    return 0;
}