1202: [HNOI2005]狡猾的商人

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?4180??Solved:?2015
[Submit][Status][Discuss]

Description

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

Input

第一行為一個(gè)正整數(shù)w，其中w < 100，表示有w組數(shù)據(jù)，即w個(gè)賬本，需要你判斷。每組數(shù)據(jù)的第一行為兩個(gè)正整數(shù)n和m，其中n < 100，m < 1000，分別表示對(duì)應(yīng)的賬本記錄了多少個(gè)月的收入情況以及偷看了多少次賬本。接下來(lái)的m行表示刁姹偷看m次賬本后記住的m條信息，每條信息占一行，有三個(gè)整數(shù)s，t和v，表示從第s個(gè)月到第t個(gè)月（包含第t個(gè)月）的總收入為v，這里假設(shè)s總是小于等于t。

Output

包含w行,每行是true或false,其中第i行為true當(dāng)且僅當(dāng)?shù)趇組數(shù)據(jù)，即第i個(gè)賬本不是假的；第i行為false當(dāng)且僅當(dāng)?shù)趇組數(shù)據(jù)，即第i個(gè)賬本是假的。

Sample Input

2
3 3
1 2 10
1 3 -5
3 3 -15
5 3
1 5 100
3 5 50
1 2 51

Sample Output

true
false

我圖形思維還是太弱了QAQ

短短并查集查了那么久

由題，只有當(dāng)我們直接或間接得到兩個(gè)相同的區(qū)間信息不同時(shí)為false

按照前綴和的思想，區(qū)間和[a,b] = z可以寫(xiě)成s[b] - s[a - 1] = z

這樣子我們就轉(zhuǎn)化為了兩個(gè)點(diǎn)之間的關(guān)系，每當(dāng)我們得出兩點(diǎn)的關(guān)系時(shí)，我們將它們所在集合合并

兩點(diǎn)關(guān)系確定，當(dāng)且僅當(dāng)兩點(diǎn)在同一并查集中

我們?cè)倬S護(hù)每一點(diǎn)到所在并查集根節(jié)點(diǎn)的距離表示s[a] - s[root]

這樣當(dāng)我們需要b - a的時(shí)，只需將d[b] - d[a]

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long int #define REP(i,n) for (int i = 1; i <= (n); i++) #define fo(i,x,y) for (int i = (x); i <= (y); i++) #define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next) using namespace std; const int maxn = 105,maxm = 100005,INF = 1000000000; inline int read(){int out = 0,flag = 1;char c = getchar();while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}return out * flag; } int pre[maxn],d[maxn],n,m; inline int find(int u){if (u == pre[u]) return u;int fa = find(pre[u]);d[u] += d[pre[u]];pre[u] = fa;return fa; } void init(){n = read(); m = read();for (int i = 0; i <= n; i++) pre[i] = i,d[i] = 0; } int main() {int T = read(),a,b,fa,fb,z;bool flag;while (T--){init(); flag = true;while (m--){a = read() - 1; b = read(); z = read(); fa = find(a); fb = find(b);if (fa != fb){d[fa] = d[b] - d[a] - z;pre[fa] = fb;}else if (d[b] - d[a] != z) flag = false;}if (flag) printf("true\n");else printf("false\n");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Mychael/p/8282808.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1202 [HNOI2005]狡猾的商人 【并查集】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。