hdu3047 Zjnu Stadium【带权并查集】

<转载于 >>> >

题目大意：

有n个人坐在zjnu体育馆里面，然后给出m个他们之间的距离， A B X，代表B的座位比A多X. 然后求出这m个关系之间有多少个错误，所谓错误就是当前这个关系与之前的有冲突。

解题分析：

（1）弄清题意，找出出现冲突的位置，判断冲突很简单就是当两个人在同一行坐，同时他们到根节点的距离差值正好是他们之间的差值，此时就出现了冲突了。

（2）关键有两个地方，这也是并查集题目的难点，就是压缩集合，和求节点到根的距离。这里压缩集合就很简单了，一个通用的递归。求到跟的距离dist[a] += dist[tem]; dist[rb]=dist[a]+x-dist[b];注意这两行代码，这是核心代码，首先第一行是求出节点a到根的距离。第二行代码使用的是数学中向量计算的原理如图

注意x是指b->a

这道题我还是很不明白，为什么连

3 2

1 2 150

2 3 150

这组数据输出的都是0，我觉得应该是1.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn=5e4+;

int n,m,ans;

int fa[maxn];

int r[maxn];

int find(int x){

    if(fa[x]==x)return x;

    int temp=fa[x];

    fa[x]=find(fa[x]);

    r[x]=(r[x]+r[temp])%;

    return fa[x];

}

void Uion(int a,int b,int c){

    int ra=find(a);

    int rb=find(b);

    if(ra==rb){

        if((r[a]-r[b]+)%!=c)ans++;      //这里意味着原来所确定a、b之间的关系与现在a、b给定的关系发生冲突，所以ans++

    }

    else{

        fa[ra]=rb;

        r[ra]=(c-r[a]+r[b]+)%;          //矢量求解ra到rb的距离

    }

}

int main(){

    while(scanf("%d %d",&n,&m)!=EOF){

        for(int i=;i<=n;i++){

            fa[i]=i;

            r[i]=;

        }

        ans=;

        for(int i=;i<=m;i++){

            int a,b,c;

            scanf("%d %d %d",&a,&b,&c);

            Uion(a,b,c);

        }

        printf("%d\n",ans);

    }

    return ;

}

2018-08-14

巴特西

hdu3047 Zjnu Stadium【带权并查集】

最新文章

热门文章