BZOJ 1202: [HNOI2005]狡猾的商人 [带权并查集]-白红宇

BZOJ 1202: [HNOI2005]狡猾的商人 [带权并查集]

阅读量：5240 次

发布时间：2019-06-14

本文共 1199 字，大约阅读时间需要 3 分钟。

题意：

给出m个区间和，询问是否有区间和和之前给出的矛盾

NOIp之前做过hdu3038.....

带权并查集维护到根的权值和，向左合并

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=1e6+5;typedef long long ll;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 n, m, l, r, v;int fa[N], val[N];int find(int x) {    if(x == fa[x]) return x;    int root = find(fa[x]);    val[x] += val[fa[x]];    return fa[x] = root;}int main() {    freopen("in", "r", stdin);    int T=read();    while(T--) {        n=read()+1; m=read();        for(int i=1; i<=n; i++) fa[i]=i, val[i]=0;        int flag=1;        for(int i=1; i<=m; i++) {            l=read(); r=read()+1; v=read();            if(!flag) continue;            int x = find(l), y = find(r); //printf("hi %d %d  %d %d  %d %d\n", l,r,x,y,val[l],val[r]);            if(x == y) {                if(val[r] - val[l] != v) flag = 0;             } else fa[y] = x, val[y] = v - val[r] + val[l];        }        puts(flag ? "true" : "false");    }}