bzoj1202 [HNOI2005]狡猾的商人

本文主要是介绍bzoj1202 [HNOI2005]狡猾的商人，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj1202
题目大意：
账本上记录了n个月以来的收入情况，其中第i 个月的收入额为Ai。当 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个账本是假的。

题解：
正解带权并查集？而我乱搞水过了。。n才小于等于100
我先说下乱搞做法：
直接设f[i][j]表示从第i个月到第j个月（包含第j个月）的总收入。
然后跑一遍像floyd的东西判断是否有矛盾就好了。

带权并查集的话就是经典的那种模型了。
设d[i]表示从第i+1个月到第fa[i]个月的总收入。
维护一下就好了。
主要是题目中是[s,t]，是闭区间。我们要把它改成半开半闭，类似(s,t]这样的。
直接输入的时候x--就好了

乱搞版

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;int f[110][110];bool bo[110][110];
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int T,n,m,x,y,c,k,i,j;scanf("%d",&T);while (T--){scanf("%d%d",&n,&m);memset(f,0,sizeof(f));memset(bo,0,sizeof(bo));for (i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&c);f[x][y]=c;bo[x][y]=true;}bool bk=true;for (k=1;k<=n;k++)for (i=1;i<=k;i++) if (bo[i][k])for (j=k+1;j<=n;j++) if (bo[k+1][j]){if (bo[i][j]) {if (f[i][k]+f[k+1][j]!=f[i][j]) {bk=false;break;}}else f[i][j]=f[i][k]+f[k+1][j],bo[i][j]=true;}if (bk) printf("true\n");else printf("false\n");}return 0;
}

带权并查集版

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;int fa[110],d[110];
int ffind(int x)
{if (x!=fa[x]){int fx=fa[x];fa[x]=ffind(fa[x]);d[x]=d[x]+d[fx];}return fa[x];
}
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int T,n,m,x,y,c,k,i,j;scanf("%d",&T);while (T--){scanf("%d%d",&n,&m);for (i=0;i<=n;i++) fa[i]=i,d[i]=0;bool bk=true;for (i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&c);x--;int fx=ffind(x),fy=ffind(y);if (fx!=fy){fa[fx]=fy;d[fx]=d[y]+c-d[x];}else if (d[x]-d[y]!=c) bk=false;}if (bk) printf("true\n");else printf("false\n");}return 0;
}