BZOJ1202: [HNOI2005]狡猾的商人
【传送门：BZOJ1202】
简要题意：
给出T组数据，每组数据有n个点，每个点都有值，给出m个区间和，判断是否所有区间和都合法
题解：
乍一眼，就是前缀和的处理，但并没有想到做法，后来发现并查集维护前缀和好像行得通，而且网上的神犇们都用并查集，而且似乎叫做带权并查集
注意当求i点祖先时，要记得对v数组进行处理
v[i]表示i到i的祖先的和，当x和y为相同祖先时，只要判断v[y]-v[x]是否等于k就能判断是否合法了，如果不是相同祖先就合并，并且对v数组进行处理
其实这道题还可以用差分约束过掉，甚至有神犇用玄学贪心过了，在此收我一膜
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int fa[110],v[110]; int findfa(int x) { if(fa[x]==x) return x; int f=fa[x]; fa[x]=findfa(fa[x]); v[x]+=v[f]; return fa[x]; } int main() { int T; scanf("%d",&T); while(T--) { memset(v,0,sizeof(v)); int n,m; scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) fa[i]=i; bool bk=true; for(int i=1;i<=m;i++) { int x,y,k; scanf("%d%d%d",&x,&y,&k); if(bk==false) continue; int fx=findfa(x-1),fy=findfa(y); if(fx==fy) { if(v[y]-v[x-1]!=k) { bk=false;continue; } } else { fa[fy]=fx; v[fy]=k-v[y]+v[x-1]; } } if(bk==false) printf("false "); else printf("true "); } return 0; }