DGZX1523 - 食物链


本题考察扩展并查集。

对于这道题,多开辟一个数组来保存天敌关系怎么样?比如读入一个“天敌”关系的时候,就修改“天敌”数组的相应位置,但天敌又有天敌,处理当前天敌关系的时候,对于天敌的天敌是否也需要进行相应修改呢?

其实本题有一种非常巧妙的做法,用一个数组father表示合并后的树,用数组rank表示节点和其父节点之间的关系。

rank[x] 表示x与father[x]的关系

rank[x] = 0 表示x与 father[x] 是同类

rank[x] = 1 表示x吃 father[x](等价于rank[x]=-2)

rank[x] = 2 表示 father[x] 吃x(等价于rank[x]=-1)

这样子定义,使得节点之间的关系满足向量运算。比如:

如果用rank<a,b>表示a指向b的向量,有:rank<1,3>:=rank<1,2>+rank<2,3>。(注意符号差别,rank<1, 3> 和 rank[1] 含义不同!)

在执行查找操作得到时候,需要同时进行路径压缩。对于上图来说,查找节点1的时候,要将节点1指向其根节点,也就是说原来rank[1]代表rank<1,2>,查找完毕后rank[1]代表rank<1,3>。

不妨自己用赋值法验证一下:

rank[1] := (rank[1]+rank[father[1]]) % 3

所以查找函数可以这么写:

【伪代码】

int find(int x)
{
    int t;
    if(x<>father[x])
    {
        t := father[x];
        father[x]:= find(father[x]);// 通过递归保证父节点的rank值先更新
        // 更新x与father[x]的关系
        rank[x] := (rank[x]+rank[t]) % 3;
    }
    exit (father[x]);
}

rank之间不仅可以进行向量加法,还可以进行减法。合并函数可以这么写:

【伪代码】

void merge(int pa, int pb, int d)
{
    int fa := find(pa);
    int fb := find(pb);
    // 将集合 fa 合并到 fb 集合上
    father[fa] := fb;
    // 更新 fa 与 father[fa] 的关系
    rank[fa] := (rank[pb] - rank[pa] + 3 + d) % 3;
}

已知的是rank<pa,pb>,rank<pa,fa>,rank<pb,fb>,要求rank<fa,fb>,有

rank<fa,fb>:=-rank<pa,fa>+rank<pa,pb>+rank<pb,fb>

记得刚才说过吗,-1等价于2,-2等价于1。

#include <stdio.h>

const int lmt = 50001;
int father[lmt], re[lmt];
int n, k;
int d, x, y;
int ans;

void merge(int pa, int pb, int d);
int find(int x);

int main()
{
	int i;
	scanf("%d%d",&n,&k);
	for (i=1; i<=n; i++)
	{
		father[i] = i;
		re[i] = 0;
	}
	for (i=1; i<=k; i++)
	{
		scanf("%d %d %d",&d,&x,&y);
		if ((d==2 && x==y) || x>n || y>n)
		{
			ans++;
			continue;
		}
		else
        {
            int fa = find(x);
            int fb = find(y);
            // 如果 x,y 的父节点相同 ,那么可以判断给出的关系是否正确的 
            if (fa==fb)
            {
                if ((re[x]-re[y]+3)%3!=d-1)// 因为已经 find 过一次,所以 x 和 y 都直接挂在根节点下面了
                    ++ans;                     
            }
            else
            {
                // 否则合并x,y 
                merge(x,y,d-1);
            }
		}
	}

	printf("%d\n",ans);
	return 0;
}

void merge(int pa, int pb, int d)
{
	int fa = find(pa);
	int fb = find(pb);
    // 将集合 fa 合并到 fb 集合上 
    father[fa] = fb;
    // 更新 fa 与 father[fa] 的关系 
    re[fa] = (re[pb] - re[pa] + d + 3) % 3;
}

int find(int x)
{
	int root = x;
	int tol = 3;
	// 寻找根节点
	while (father[root]!=root)
	{
		tol += re[root];
		root = father[root];
	}
	int t = x, p;
    if(t!=root)
    {
		// 修改 rank 值
		p = re[t];
		re[t] = tol % 3;
		tol -= p;
		// 路径压缩
        p = father[t];
        father[t] = root;
		t = p;
    }
    return father[x];
}

优质内容筛选与推荐>>
1、js中函数提升及var变量提示
2、Attribute在拦截机制上的应用
3、iPhone开发之深入浅出 (1) — ARC是什么
4、PAT1017
5、时间格式化成英文 02 nov 2014


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号





    联系我们

    欢迎来到TinyMind。

    关于TinyMind的内容或商务合作、网站建议,举报不良信息等均可联系我们。

    TinyMind客服邮箱:support@tinymind.net.cn