hdu 3038 How Many Answers Are Wrong（种类并查集）2009 Multi-University Training Contest 13

了解了种类并查集，同时还知道了一个小技巧，这道题就比较容易了。

其实这是我碰到的第一道种类并查集，实在不会，只好看着别人的代码写。最后半懂不懂的写完了。然后又和别人的代码进行比较，还是不懂，但还是交了。

现在回过头来看，又看了一遍。

题意——

输入——

给出多组测试数据。

每组数据第一行包含两个整数n, m。n表示共有1——n这么多个数，m表示m组提示。

接下来m行，每行包含三个整数a, b, val。表示从a到b这几个数的和为val。

这几组数有可能有冲突，问一共有多少组有冲突的数据。

输出——

输出有冲突的数据的数量。

举例——

10 5

1 10 100

7 10 28

1 3 21

4 6 41

6 6 1

其中前三组数据明确4——6几个数的和为40，而第四组数据表示4——6几个数的和为41，那么这一组数据就是有冲突的。所以这组测试数据的输出为1。

那么分种类就行了。这里其实种类并不明显，或者说并不是标准的种类，只是算法设计上借鉴了种类并查集的思想（也可能是我对这个还不太理解）。这里使用了一个数组来存储n个数之间的相对关系（即a到b的和）。

假如a到b的和为val，a当前所存的值为x，那么b的值修改为x+val，如果b的值已经有了，且！=x+val，那么冲突数+1。

一个小技巧——

除此之外，还有一点需要注意，1——7和7——10不能直接按照1——10进行合并。如果是1——6和7——10，那么可以合并为1——10。所以，我采取的方法是使用a-1和b进行合并。即将1——6看做0——6，将7——10看做6——10，所以合并出来就是0——10。

种类并查集：hdu1829—— http://www.cnblogs.com/mypride/p/4743357.html

小技巧：hdu3461—— http://www.cnblogs.com/mypride/p/4671926.html

上代码——

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 200010;
const int M = 40010;

int sum[N], fm[N];      //sum[]数组表示任意区间内的数的相对的和。
int n, m;
int x, y, val;
int ans;

int mfind(int x)
{
    if(x == fm[x]) return x;
    int fx = fm[x];
    fm[x] = mfind(fm[x]);
    sum[x] += sum[fx];      //及时修改sum[]数组，即，第x个数到当前根节点之间的差值（或者说和）。
    return fm[x];
}

void mmerge(int x, int y, int val)
{
    int fx = mfind(x);
    int fy = mfind(y);
    if(fx == fy)
    {
        if(sum[y]-sum[x] != val) ans++;
    }
    else
    {
        fm[fy] = fx;
        sum[fy] = sum[x]-sum[y]+val;        //及时修改sum[]数组，即，两个根节点之间的差值（或者说和）。
    }
    //for(int i = 0; i <= n; i++) printf("%4d", sum[i]);
    //printf("
");
}

void init()
{
    for(int i = 0; i <= n; i++)
    {
        sum[i] = 0;             //初始化差值
        fm[i] = i;
    }
    ans = 0;
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &x, &y, &val);
        mmerge(x-1, y, val);
    }
}

int main()
{
    //freopen("test.in", "r", stdin);
    while(~scanf("%d%d", &n, &m))
    {
        init();
        printf("%d
", ans);
    }
    return 0;
}