题解 | #[HNOI2005]狡猾的商人#

题目描述

刁姹接到一个任务，为税务部门调查一位商人的账本，看看账本是不是伪造的。

账本上记录了 $nn$ 个月以来的收入情况，其中第 $ii$ 个月的收入额为 $A_i(i=1,2,\mathrm{3...}n-1,n)A\_i(i=1,2,3...n-1,n)$。

当 $A_{i}A\_i$ 大于 $00$ 时表示这个月盈利 $A_{i}A\_i$ 元，当 $A_{i}A\_i$ 小于 $00$ 时表示这个月亏损 $A_{i}A\_i$ 元。所谓一段时间内的总收入，就是这段时间内每个月的收入额的总和。

刁姹的任务是秘密进行的，为了调查商人的账本，她只好跑到商人那里打工。

她趁商人不在时去偷看账本，可是她无法将账本偷出来，每次偷看账本时她都只能看某段时间内账本上记录的收入情况，并且她只能记住这段时间内的总收入。

现在，刁姹总共偷看了 $mm$ 次账本，当然也就记住了 $mm$ 段时间内的总收入，你的任务是根据记住的这些信息来判断账本是不是假的。

思路

差分约束完整理解

1. 用 $S[i]S[i]$ 表示前 $ii$ 个月的盈利总和，由题意则有 $S[t]-S[s-1]=vS[t]\; -\; S[s\; -\; 1]\; =\; v$，对于账本是否有假，也就对应了图中是否存在环。
2. 如果建图按照最短路，则判断是否有负环；如果建图按照最长路，则判断是否有正环。
3. • 按照最短路建图：由 $S[t]-S[s-1]=v\iff S[t]\le S[s-1]+v\mathrm{和}S[s-1]\le S[t]-vS[t]\; -\; S[s\; -\; 1]\; =\; v\; \backslash Leftrightarrow\; S[t]\; \backslash leq\; S[s\; -\; 1]\; +\; v\; 和\; S[s\; -\; 1]\; \backslash leq\; S[t]\; -\; v$。
   • 按照最长路建图：由 $S[t]-S[s-1]=v\iff S[s-1]\ge S[t]-v\mathrm{和}S[t]\ge S[s-1]+vS[t]\; -\; S[s\; -\; 1]\; =\; v\; \backslash Leftrightarrow\; S[s\; -\; 1]\; \backslash geq\; S[t]\; -\; v\; 和\; S[t]\; \backslash geq\; S[s\; -\; 1]\; +\; v$。

AC 代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 2010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N], q[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa()
{
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);
    
    int hh = 0, tt = 1;
    q[0] = 0;
    dist[0] = 0, st[0] = true;
    
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return false;
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    
    return true;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &m);
        
        memset(h, -1, sizeof h);
        idx = 0;
        while (m -- )
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(b, a - 1, c), add(a - 1, b, -c);
        }
        
        if (spfa()) puts("true");
        else puts("false");
    }
    
    return 0;
}