BZOJ1202: [HNOI2005]狡猾的商人(帶權並查集)

Description

刁奼接到一個任務，為稅務部門調查一位商人的賬本，看看賬本是不是偽造的。賬本上記錄了n個月以來的收入情況，其中第i 個月的收入額為Ai(i=1,2,3...n-1,n)， 。當 Ai大於0時表示這個月盈利Ai 元，當 Ai小於0時表示這個月虧損Ai 元。所謂一段時間內的總收入，就是這段時間內每個月的收入額的總和。 刁奼的任務是秘密進行的，為了調查商人的賬本，她只好跑到商人那裡打工。她趁商人不在時去偷看賬本，可是她無法將賬本偷出來，每次偷看賬本時她都只能看某段時間內賬本上記錄的收入情況，並且她只能記住這段時間內的總收入。 現在，刁奼總共偷看了m次賬本，當然也就記住了m段時間內的總收入，你的任務是根據記住的這些信息來判斷賬本是不是假的。

Input

第一行為一個正整數w，其中w < 100，表示有w組數據，即w個賬本，需要你判斷。每組數據的第一行為兩個正整數n和m，其中n < 100，m < 1000，分別表示對應的賬本記錄了多少個月的收入情況以及偷看了多少次賬本。接下來的m行表示刁奼偷看m次賬本後記住的m條信息，每條信息占一行，有三個整數s，t和v，表示從第s個月到第t個月（包含第t個月）的總收入為v，這裡假設s總是小於等於t。

Output

包含w行,每行是true或false,其中第i行為true當且僅當第i組數據，即第i個賬本不是假的；第i行為false當且僅當第i組數據，即第i個賬本是假的。

Sample Input

Sample Output

HINT

Source

看不懂

我寧願寫差分約束

告辭

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#define LL long long  
const int MAXN = 1e5 + 10, INF = 1e9 + 10;
using namespace std;
inline int read() {
    char c = getchar();int x = 0,f = 1;
    while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();}
    return x * f;
}
int QwQ;
int N, M, fa[MAXN], val[MAXN];
int find(int x) {
    if(fa[x] == x) return x;
    int f = find(fa[x]);
    val[x] += val[fa[x]];
    fa[x] = f;
    return f;
}
main() {
    //freopen("bzoj_1202.in", "r", stdin);
//    freopen("bzoj_1202.out", "w", stdout);
    QwQ = read();
    while(QwQ--) {
        N = read(); M = read();
        for(int i = 0; i <= N; i++) fa[i] = i, val[i] = 0;
        bool flag = 0;
        for(int i = 1; i <= M; i++) {
            int x = read() - 1, y = read(), w = read();
            int fx = find(x), fy = find(y);
            if(fx == fy) {
                if(val[y] - val[x] != w) flag = 1;
            } else {
                val[fx] = val[y] - val[x] - w;
                fa[fx] = fy;
            }
        }
        puts(!flag ? "true" : "false");
    }
}