首页 > 其他 > 详细

HDU-3038 How Many Answers Are Wrong 并查集

时间:2019-04-24 16:58:33      阅读:122      评论:0      收藏:0      [点我收藏+]

题目链接:https://vjudge.net/problem/HDU-3038

题意:

这里的n表示有一个长度为n的数组, 接下来有m行形如x, y, d的输入, 表示从第x个元素到第y个元素的和为d(包括x和y), 问m行输入里面有几个是错误的(保证第一个输入是正确的)。

分析:

首先因为条件是给出元素之间链接关系,所以想到是并查集,又由于记录了两元素之间的额外信息(第x个元素到第y个元素的和),所以是带权并查集问题。

代码中的核心在于两部分,一是查找根元素函数find(),在每次查找的过程中都对元素和其根元素之间的距离做维护更新,以此实现图的构建和更新。二是而是在录入数据的过程中对带权并查集的更新和验证,当两点的根节点不同时,就将其加入并查集,更新根节点和权重,当根相同时,即在之前已经出现过和这两点有关的数据,则验证输入是否正确,记录错误输入的个数即可。

代码中最核心的将新的关系加入并查集的代码:

fa[fx] = fy;   (1)

val[fx] = val[y] - val[x] + z;   (2)

式(1)好理解,就是将y的根当作现在x的根fx的根,即将x所在的链加入到y所在的链上。

式(2)可以通过如下图来理解:

技术分享图片

其中红色为待求部分,看图则很容易理解并得到上面的式(2)。

代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 200010;
int n, m, x, y, z, ans = 0;
int fa[maxn];
int val[maxn];

void init() {
    for(int i = 0; i <= n; i++) {
        fa[i] = i;
        val[i] = 0;
    }
    ans = 0;
}

int find(int x) {
    if(x == fa[x])
        return x;
    int tmp = x;
    while(x != fa[x]) {
        val[tmp] += val[fa[x]];
        x = fa[x];
    }
    fa[tmp] = x;
    return x;
}

int main(void) {
    while(scanf("%d%d", &n, &m) == 2) {
        init();
        for(int i = 0; i< m; i++) {
             scanf("%d%d%d", &x, &y, &z);
             x--;
             int fx = find(x);
             int fy = find(y);
             if(fx != fy) {
                 fa[fx] = fy;
                 val[fx] = val[y] - val[x] + z;
            }
            else {
                if(val[x] - val[y] != z)
                    ans++;
            }
        }
        printf("%d\n", ans);
    }    
}

HDU-3038 How Many Answers Are Wrong 并查集

原文:https://www.cnblogs.com/RB26DETT/p/10763263.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!