# [hnoi2005] 狡猾的商人

## 0. 题目描述

**题面**:[P2294 [HNOI2005]狡猾的商人](https://www.luogu.com.cn/problem/P2294)

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

## 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 坑点

* **区间**

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

  **例如**:题目的样例第二组

  ```
  5 3
  1 5 100
  3 5 50
  1 2 51
  ```

  如果按照读入的数据建图，画成图就是这样子的:

    ![wrong](https://cdn.luogu.com.cn/upload/image_hosting/71qzac3a.png)

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

    ![correct](https://cdn.luogu.com.cn/upload/image_hosting/8x67x3cb.png)

  于是图就连上了，同时因为 \\( 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

```cpp
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1010;

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

int read() {
    int res = 0;
    char c = getchar();
    bool flag = 0;
    while (c > '9' || c < '0') {
        if (c == '-') flag = 1; // 快读记得特判负数
        c = getchar();
    }
    while (c >= '0' && c <= '9') res = res * 10 + c - 48, c = getchar();
    return flag ? -res : res;
}

void add(int x, int y, int e ) {
    ver[++tot] = y;
    w[tot] = e;
    nxt[tot] = head[x];
    head[x] = tot;
}

void init() {
    memset(nxt, 0, sizeof(nxt));
    memset(ver, 0, sizeof(ver));
    memset(w, 0, sizeof(w));
    memset(head, 0, sizeof(head));
    memset(v, 0, sizeof(v));
    tot = 0; // 记得初始化 tot
}

bool spfa(int s) {
    bool exist[N];
    memset(exist, 0, sizeof(exist));
    memset(d, 0, sizeof(d)); // 这个每次都要重置，因为每个连通块，起点不同
    queue<int> q;
    q.push(s);
    v[s] = exist[s] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        exist[x] = 0;
        for (int i = head[x]; i; i = nxt[i]) {
            int &y = ver[i], &e = w[i];
            if (d[y] == d[x] + e || d[y] == 0) { // d[y] == 0 时，这个点没被更新，需要更新一次
                d[y] = d[x] + e;
                if (!exist[y]) {
                    exist[y] = 1;
                    q.push(y);
                }
            }
            else return false; // 不相等直接就是false
        }
    }
    return true; // 一个块内所有的点都没问题才是true
}

int main() {
    int T = read();
    while (T--) {
        init(); // 记得初始化
        n = read(), m = read();
        for (int i = 1; i <= m; ++i) {
            int x = read(), y = read(), z = read();
            add(x - 1, y, z); // 前开后闭
        }
        bool flag = 0;
        for (int i = 0; i <= n; ++i) {
            if (v[i]) continue;
            if (!spfa(i)) { // 一个是false这组数据就直接是false
                printf("false\n");
                flag = 1;
                break;
            }
        }
        if (!flag) {
            printf("true\n"); // 每一个都是true，这组数据就是true
        }
    }
    return 0;
}
```