并查集可以加入统计量,来统计某个等价类的性质。并且,通过在合并时更新,可以保留此类性质。

差统计量 维护的是两个节点之间差的统计量。有人将此类归作种类并查集,但其本质上维护的是两个节点之间差的值,并且通过合并来逐步完善差的关系。

进一步的解释:如果若干个元素在同一个集合中(从fa[x]可以观察出来),那么这个集合中任意两个元素x,y的差值rk[y]-rk[x]是一定的。
如果询问:所给的两个元素是否在同一个集合中/求两个元素的差值/求某一统计量,其可以间接转化为两个元素的差值/...,我们就可以通过判断rk[y]-rk[x]是否与询问一致/返回rk[y]-rk[x]的值来解决。

分析如下例子:
HDU 3038 How Many Answers Are Wrong
大致思路:这题就相当于判断两个元素的差统计量是否与所给的值矛盾,很明显,若两区间端点相邻或重合,我们就可以求出这些子区间及子区间合并后的区间的元素和。我们可以将区间变为左闭右开的形式(即区间右端点+1),然后合并两端点。
直接看样例:
一开始初始化所有rk[i]为0,并在接下来的合并x,y中保持fa[y]->fa[x](固定合并方向)
1 10 100 -> 合并1,11,rk[1]=0,rk[11]=100
7 10 28 -> 合并7,11,相当于合并7,1,求相对值后rk[1]=-72,rk[7]=0,rk[11]=28
1 3 32 -> 合并1,4,相当于合并7,4,求相对值后rk[4]=-40,其余不变
4 6 41 -> 发现4,7在同一个集合中,但rk[7]-rk[4]=0-(-40)=40,矛盾
6 6 1 -> 合并6,7,rk[7]=1,更新各节点之后rk[1]=-71,rk[4]=-39,rk[6]=0,rk[7]=1,rk[11]=29

代码:

/*62ms,1772KB*/

int fa[mx], rk[mx];

int find(int x)
{
    int tmp = fa[x];
    if (~tmp)
    {
        fa[x] = find(tmp);
        rk[x] += rk[tmp]; ///从根部开始更新节点
     return fa[x];
    }
    return x;
}

int main()
{
    int n, m, cnt, x, y, fax, fay, s;
    while (~RII(n, m))
    {
        mem(fa, -1), mem(rk, 0);
        cnt = 0;
        while (m--)
        {
            RIII(x, y, s), ++y;
            fax = find(x), fay = find(y);
            if (fax != fay)
            {
                fa[fay] = fax;
                rk[fay] = rk[x] - rk[y] + s; ///求相对值,解释见下
         }
            else if (rk[y] - rk[x] != s) ++cnt;
        }
        PI(cnt);
    }
    return 0;
}


如图,rk[3]=10,rk[10]=100,此时更新10到3的相对差为200,所以rk[10]应该为210,再由rk[10]推出rk[8]=210-100=110。一般化这个思路,我们有rk[x]+s=rk[fay]+rk[y],即rk[fay]=rk[x]-rk[y]+s

理解上面那个代码之后,POJ 1182 食物链那样的题也就好思考了:同样是维护差统计量,判断的时候求(rk[y]-rk[x])%3的值就行。具体实现见这里

再看一个需要考虑合并两个集合时合并的方向的问题:URAL 1701 Ostap and Partners

代码:

/*0.171s,745KB*/

int fa[mx], rk[mx];

int find(int x)
{
    int tmp = fa[x];
    if (~tmp)
    {
        fa[x] = find(tmp);
        rk[x] += rk[tmp]; ///从根部开始更新节点
     return fa[x];
    }
    return x;
}

int main()
{
    int n, m, x, y, fax, fay, d, i, tmp;
    mem(fa, -1), RII(n, m);
    For(i, m)
    {
        RIII(x, y, d);
        fax = find(x), fay = find(y);
        if (fax != fay)
        {
            /// 保证不会产生负数工资,以此为基础更新
         tmp = rk[y] - rk[x] + d;
            if (tmp > 0) fa[fax] = fay, rk[fax] = tmp;
            else if (tmp < 0) fa[fay] = fax, rk[fay] = -tmp;
            else
            {
                if (fax) fa[fax] = fay, rk[fax] = 0;
                else fa[fay] = fax, rk[fay] = 0;
            }
            if (find(0)) break;
        }
        else if (rk[x] - rk[y] != d) break;
    }
    if (i < m) printf("Impossible after %d statements\n", i + 1);
    else
    {
        puts("Possible");
        For(i, n) find(i), PI(rk[i]);
    }
    return 0;
}

Comments

comments powered by Disqus