0. 题目描述#

题面:P2294 [HNOI2005]狡猾的商人

检查一个商人的账本是否是伪造的(~~缩句大师~~)，简单来说就是对于每一组数据，每个区间内的盈利总和应该一致，否则就是伪造的

1. 心路历程#

其实看了描述就跟没看一样懵，因为这道题涉及到区间和之类的东西，所以我的第一反应是线段树维护区间和，但是后来发现这样不行，因为你只知道一个区间的总和，并不知道每个子区间的详细信息，所以当输入的一个区间横跨线段树的两个节点时就没办法处理了。所以不可以用维护区间和的思想。

所以要想一个别的方法巧妙地解决这个问题，因刚学了差分约束系统，所以我简单地想到了图论

2. 解析#

2.1 建边#

对于每个区间 $[l, r]$ ，都建一条边 $(l - 1)$ -> $r$ ，边权为盈利值 $a$

2.2 思路#

也很简单，如果一个区间 $(l, r]$ 的盈利值是 $a$ ，那么所有由 $l$ 指向 $r$ 的路径的长度应该都为 $a$ ，否则就是假的。

计起点到第 $i$ 个点的距离为 $d[i]$ ，那么当存在一条起点为 $x$ 终点为 $y$ 边权值为 $a$ 的边满足 $d[y] \neq d[x] + a$ 时，这个账单是假的。

2.3 坑点#

区间

所有的区间都要改成一开一闭（我这里是前开后闭），如果按照题目的读入直接建边就会面临一定的问题。

例如:题目的样例第二组
```
1
5 3
2
1 5 100
3
3 5 50
4
1 2 51
```
如果按照读入的数据建图，画成图就是这样子的:

显然这个是错的， $2$ 和 $3$ 是相连的。但是如果把区间 $[l, r]$ 改成一开一闭，即 $(l-1,r]$ ，图就会变成这样:

于是图就连上了，同时因为 $51+50 \neq 100$ ，所以答案是 $false$ 。
多起点SPFA

因为图中的每个连通块都是相互独立，互不干扰的（每个极大区间相互独立），所以对于每一个连通块都独立地跑一遍SPFA
判断条件
1. 对于每一个连通块内，当 $d[y] = d[x] + w$ 或 $d[y] = 0$ 时更新 $d[y]$ ，并且将 $d[y]$ 入队，否则直接判false，全部正常跑完为true。
2. 对于整张图，存在一个连通块 false，直接是 false；所有连通块都为 true，就输出 true。

明确了思路之后就可以自己尝试写一下了，实在不会了看下面的代码。

Ac Code#

1
#include <cstdio>
2
#include <cstring>
3
#include <queue>
4

5
using namespace std;
6

7
const int N = 1010;
8

9
int nxt[N * 4], ver[N * 4], w[N * 4], head[N]; // 前向星存图
10
int d[N]; // 距离
11
bool v[N]; // 记录是否被访问过，被访问过的点已经在别的连通块中，所以下一次就不用从这个点开始搜了
12
int tot;
13
int n, m;
14

15
int read() {
16
    int res = 0;
17
    char c = getchar();
18
    bool flag = 0;
19
    while (c > '9' || c < '0') {
20
        if (c == '-') flag = 1; // 快读记得特判负数
21
        c = getchar();
22
    }
23
    while (c >= '0' && c <= '9') res = res * 10 + c - 48, c = getchar();
24
    return flag ? -res : res;
25
}
26

27
void add(int x, int y, int e ) {
28
    ver[++tot] = y;
29
    w[tot] = e;
30
    nxt[tot] = head[x];
31
    head[x] = tot;
32
}
33

34
void init() {
35
    memset(nxt, 0, sizeof(nxt));
36
    memset(ver, 0, sizeof(ver));
37
    memset(w, 0, sizeof(w));
38
    memset(head, 0, sizeof(head));
39
    memset(v, 0, sizeof(v));
40
    tot = 0; // 记得初始化 tot
41
}
42

43
bool spfa(int s) {
44
    bool exist[N];
45
    memset(exist, 0, sizeof(exist));
46
    memset(d, 0, sizeof(d)); // 这个每次都要重置，因为每个连通块，起点不同
47
    queue<int> q;
48
    q.push(s);
49
    v[s] = exist[s] = 1;
50
    while (!q.empty()) {
51
        int x = q.front();
52
        q.pop();
53
        exist[x] = 0;
54
        for (int i = head[x]; i; i = nxt[i]) {
55
            int &y = ver[i], &e = w[i];
56
            if (d[y] == d[x] + e || d[y] == 0) { // d[y] == 0 时，这个点没被更新，需要更新一次
57
                d[y] = d[x] + e;
58
                if (!exist[y]) {
59
                    exist[y] = 1;
60
                    q.push(y);
61
                }
62
            }
63
            else return false; // 不相等直接就是false
64
        }
65
    }
66
    return true; // 一个块内所有的点都没问题才是true
67
}
68

69
int main() {
70
    int T = read();
71
    while (T--) {
72
        init(); // 记得初始化
73
        n = read(), m = read();
74
        for (int i = 1; i <= m; ++i) {
75
            int x = read(), y = read(), z = read();
76
            add(x - 1, y, z); // 前开后闭
77
        }
78
        bool flag = 0;
79
        for (int i = 0; i <= n; ++i) {
80
            if (v[i]) continue;
81
            if (!spfa(i)) { // 一个是false这组数据就直接是false
82
                printf("false\n");
83
                flag = 1;
84
                break;
85
            }
86
        }
87
        if (!flag) {
88
            printf("true\n"); // 每一个都是true，这组数据就是true
89
        }
90
    }
91
    return 0;
92
}

Star's Blog