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

• 区间

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

  例如:题目的样例第二组

  5 3
  1 5 100
  3 5 50
  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

#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;
}