差分约束杂题选讲

十月 17, 2020 10721

题面自己找，这里只讲思路。

HDU 3592 World Exhibition

线性约束板子题。和 POJ3169 Layout 相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Accepted

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;

using std::cin;
using std::cout;
using std::endl;

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

const int MAXN = 10000 + 10;

struct Edge {
    int v, w;
    Edge(int _v = 0, int _w = 0) : v(_v), w(_w) {}
};

int n, x, y;
std::vector<Edge> G[MAXN];

int spfa(int s) {
    static int dist[MAXN]; memset(dist, 0x3f, sizeof dist);
    static bool inq[MAXN]; memset(inq, 0, sizeof inq);
    static int vis[MAXN]; memset(vis, 0, sizeof vis);
    std::queue<int> q; q.push(s);
    dist[s] = 0; inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        ++vis[u];
        if (vis[u] > n) return -1;
        for (int i = 0, siz = (int) G[u].size(); i < siz; ++i) {
            int v = G[u][i].v, w = G[u][i].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) inq[v] = true, q.push(v);
            }
        }
    }
    return dist[n] == 0x3f3f3f3f ? -2 : dist[n];
}

int main() {
    int T = read();
    while (T --> 0) {
        n = read(); x = read(); y = read();
        for (int i = 1; i <= x; ++i) {
            int a = read(); int b = read(); int c = read();
            // d[b] - d[a] <= c
            // a -> b : c
            G[a].push_back(Edge(b, c));
        }
        for (int i = 1; i <= y; ++i) {
            int a = read(); int b = read(); int c = read();
            // d[b] - d[a] >= c
            // d[a] - d[b] <= -c
            // b -> a : -c
            G[b].push_back(Edge(a, -c));
        }
        for (int i = 2; i <= n; ++i) {
            G[i].push_back(Edge(i - 1, 0));
        }
        for (int i = 1; i <= n; ++i) {
            G[0].push_back(Edge(i, 0));
        }
        if (spfa(0) == -1) puts("-1");
        else printf("%d\n", spfa(1));
        for (int i = 0; i <= n; ++i) G[i].clear();
    }
    return 0;
}

HDU 3440 House Man

几乎是线性约束板子题。约束是两个相邻高度的房子之间的距离， \mathcal{O}(n^2) 枚举一下就好。唯一的区别就是房子不能在同一位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// Accepted

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;

using std::cin;
using std::cout;
using std::endl;

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

/**
 *
 * 1. 低的往第一个比它高的连正权边
 * 2. 按顺序从 i 往 i - 1 连 w = -1 边
 * 3. 跑最短路
 *  
 */

const int MAXN = 1000 + 10;

struct Edge {
    int v, w; Edge(int _v = 0, int _w = 0) : v(_v), w(_w) {}
};

int n, d;
int height[MAXN];
std::vector<Edge> G[MAXN];

void cleanup() {
    for (int i = 1; i <= n; ++i) G[i].clear();
}

int spfa(int s, int t) {
    static int dist[MAXN]; memset(dist, 0x3f, sizeof dist);
    static bool inq[MAXN]; memset(inq, 0, sizeof inq);
    static int vis[MAXN]; memset(vis, 0, sizeof vis);
    std::queue<int> q;
    dist[s] = 0; q.push(s); inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        // printf("u = %d\n", u);
        ++vis[u]; if (vis[u] > n + 1) return -1;
        for (int i = 0, siz = (int) G[u].size(); i < siz; ++i) {
            int v = G[u][i].v, w = G[u][i].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) inq[v] = true, q.push(v);
            }
        }
    }
    return dist[t];
}

int main() {
    int T = read();
    for (int cas = 1; cas <= T; ++cas) {
        n = read(); d = read();
        for (int i = 1; i <= n; ++i) height[i] = read();
        printf("Case %d: ", cas);
        int hightest = 0, downh = 0;
        int lowest = 0x3f3f3f3f, downl = 0;
        for (int i = 1; i <= n; ++i) {
            int nowh = 0x3f3f3f3f, down = 0;
            if (hightest < height[i]) { hightest = height[i]; downh = i; }
            if (lowest > height[i]) { lowest = height[i]; downl = i; }
            for (int j = 1; j <= n; ++j) {
                if (height[j] < nowh && height[j] > height[i]) {
                    nowh = height[j]; down = j;
                }
            }
            // printf("downl: %d %d\n", downl, height[downl]);
            // printf("downh: %d %d\n", downh, height[downh]);
            // printf("%d %d\n", down, height[down]);

            int fx = i; if (fx > down) std::swap(fx, down);
            // d[higher] - d[lower] <= d
            if (down && fx) G[fx].push_back(Edge(down, d));
            // d[i] - d[i - 1] >= 1
            // d[i - 1] - d[i] <= -1
            if (i != 1) G[i].push_back(Edge(i - 1, -1));
        }
        if (downl > downh) std::swap(downl, downh);
        printf("%d\n", spfa(downl, downh));
        cleanup();
    }
    return 0;
}

POJ 2983 Is the information reliable?

也是线性约束板子题。设 d_i 为防御站 i 相对于某一个参考系的距离，然后照着题目写约束建边即可。

代码不放了。

HDU3666 THE MATRIX PROBLEM

整理一下柿子，可以发现约束条件：

l \leq x_{i, j} \cdot \frac{a_i}{b_j} \leq u

两边除一下常量

\frac{l}{x_{i, j} } \leq \frac{a_i}{b_j} \leq \frac{u}{x_{i, j} }

乘法和除法不满足差分约束条件，如何解决？

一个经典套路：两边取 \log 。

例：

ab \leq \frac{c}{d}\\ \Rightarrow \log_xa + \log_xb \leq \log_xc - \log_xd

底数这里用了 x 意思是取啥合法底数都可以，无论是 2, e, 10 。

所以上面的柿子等价于：

\Rightarrow\left\{ \begin{array}{l} \log a_i - \log b_i \leq \log u - \log x_{i, j}\\ \log a_i - \log b_i \geq \log l - \log x_{i, j} \end{array} \right.

其实这个柿子还是有一些问题：差分约束要求的是一组变量，这里有两组 a, b ，仍然无法直接做。

这个也好解决：令

\begin{aligned} S_{1\dots n} &= \log a_{1\dots n},\\ S_{n + 1 \dots n + m} &= \log b_{1\dots m} \end{aligned}

然后 \log a_i \rightarrow \log b_j 的边就相当于是 i \rightarrow j + n ，就可以做了。

代码不放了。至今没调出来。

BZOJ 4500 矩阵

和上一道题差不多，令 a 表示行操作的结果， b 表示列操作的结果

只不过限制变成了

a_i + b_j = c

也即

c \leq a_i - (-b_j) \leq c

所以可以令

\begin{aligned} S_{1\dots n} &= a_{1\dots n}\\ S_{n + 1 \dots n + m} &= -b_{1\dots m} \end{aligned}

所以有

c \leq S_i - S_{n + j} \leq c

差分约束即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// Accepted

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 

using std::cin;
using std::cout;
using std::endl;

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

const int MAXN = 1000 + 10;

struct Edge {
    int v, w; Edge(int _v = 0, int _w = 0) : v(_v), w(_w) {}
};

int n, m, k;
std::vector<Edge> G[MAXN << 1];

int spfa(int s, int t) {
    static long long int dist[MAXN << 1]; 
    for (int i = 0; i <= n + m; ++i) dist[i] = -2147483646;
    static bool inq[MAXN << 1]; memset(inq, 0, sizeof inq);
    static int vis[MAXN << 1]; memset(vis, 0, sizeof vis);
    std::queue<int> q; dist[s] = 0;
    q.push(s); inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        if (vis[u] > n + m) return -1;
        ++vis[u];
        for (int i = 0, siz = (int) G[u].size(); i < siz; ++i) {
            int v = G[u][i].v, w = G[u][i].w;
            if (dist[v] < dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) inq[v] = true, q.push(v);
            }
        }
    }
    return dist[t];
}

int main() {
    int T = read();
    while (T --> 0) {
        n = read(); m = read(); k = read();
        for (int i = 1; i <= k; ++i) {
            int x = read(); int y = read(); int c = read();
            // a[i] + b[j] = c
            // a[i] - (-b[j]) = c
            // c <= a[i] - (-b[j]) <= c
            // c <= S[i] - S[n + j] <= c
            // S[i] - S[n + j] >= c
            // S[n + j] - S[i] >= -c
            G[x].push_back(Edge(n + y, -c));
            G[n + y].push_back(Edge(x, c));
        }
        for (int i = 1; i <= n + m; ++i) {
            G[0].push_back(Edge(i, 0));
        }
        puts(spfa(0, n + m) == -1 ? "No" : "Yes");
        for (int i = 0; i <= n + m; ++i) {
            G[i].clear();
        }
    }
    return 0;
}