首页 > 代码库 > HDU 3038

HDU 3038

2024-08-03 03:29:46   220人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=3038

题意：[1-n]的区间，有m个询问，每个询问表示[a,b]的和是s，问一共有多少组矛盾

sum[i]表示i到根节点的和，求区间和用sum[b]-sum[a-1]

为方便描述先把a--

我是把b的父亲接在a的父亲上，下面图都是如此

1、当b和a在同一个集合，只需判断[a,b]间和是否是s，算法用向量表示，如下图

if(sum[b]-sum[a]!=s)ans++;

2、a、b不在同一个集合，把b的父亲连在a上，sum[pb]的算法如下图向量表示

sum[pb]=-sum[b]+s+sum[a];

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <queue>#include <map>using namespace std;int fa[200005],sum[200005];int find(int x){    if(x!=fa[x]){        int pre=fa[x];        fa[x]=find(fa[x]);        sum[x]+=sum[pre];    }    return fa[x];}int main(){        int n,m;    while(~scanf("%d%d",&n,&m)){        memset(sum,0,sizeof(sum));        for(int i=0;i<=n;i++)            fa[i]=i;        int ans=0;        for(int i=0;i<m;i++){            int a,b,s;            scanf("%d%d%d",&a,&b,&s);            a--;            int pa=find(a);            int pb=find(b);            if(pa!=pb){                fa[pb]=pa;                sum[pb]=-sum[b]+s+sum[a];            }            else{                if(sum[b]-sum[a]!=s)ans++;            }        }        printf("%d\n",ans);    }    return 0;}
View Code

 

HDU 3038


联系
我们