HDU-3038-How Many Answers Are Wrong

ACM模版

描述

题解

有人说这道题是种类并查集，可能是我的概念不好吧，带权并查集搞搞就行了，和HDU 3047 Zjnu Stadium几乎代码一模一样，不同的是，这个题的思路容易跑偏，可能会想到线段树（毕竟和区间挂钩了），但是，并查集搞搞就KO了……

代码

#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN = 200005;

int n, m;
int pre[MAXN];
int rank_[MAXN];

void init()
{
    for (int i = 0; i <= n; ++i)
    {
        pre[i] = i;
        rank_[i] = 0;
    }
}

int find(int x)
{
    if (x == pre[x])
    {
        return pre[x];
    }

    int t = pre[x];
    pre[x] = find(pre[x]);
    rank_[x] += rank_[t];

    return pre[x];
}

bool join(int x, int y, int m)
{
    int fx = find(x);
    int fy = find(y);

    if (fx == fy)
    {
        if (rank_[x] + m != rank_[y])
        {
            return false;
        }
        return true;
    }
    pre[fy] = fx;
    rank_[fy] = rank_[x] + m - rank_[y];
    return true;
}

int main()
{
    int a, b, x;
    while (~scanf("%d%d", &n, &m))
    {
        init();

        int cnt = 0;
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &a, &b, &x);
            if (!join(a - 1, b, x))
            {
                ++cnt;
            }
        }
        printf("%d\n", cnt);
    }

    return 0;
}

参考

HDU 3047 Zjnu Stadium