ORZ

并查集,数据结构一定要学好**!**

Flag 　　 Accepted

题号 　　P1531

类型(?) 　　并查集

通过 　　390人

提交 　　1200次

通过率 　　32%

难度 　　3

---|---|---|---|

多么优美的整数

【A>B>C>A>B>C>……

X与FA[X]关系值的本质是在此不等式中FA[X]的种类是在X的种类之后的第几个

1说明X吃FA[X]

2说明FA[X]吃X

所以FIND的时候累加关系值MOD 3就行了】——楼下下下下下下下下prince_hao

据另一位神牛说是加权并查集，不过在并查集外再开一个同样大的数组存储关系值，对其进行上述处理即可。程序短小精悍，比我以前看到的清华生分离集合的详细题解和四个程序简洁了很多很多。

gang19940521和1s的题解大致相同，均为pascal，强烈推荐。C党请看楼下的楼下。

在小胖的奇偶题解里，有神牛说做过食物链后并查集无压力。故强烈推荐此题，不知经过了多少神牛神犇的努力，才让复杂的离散数组程序变为简单的并查集。

tyvj的旧版题解里讲关系值比较详细，摘录如下：

【本题是一道“确定关系”的题，但关系比较复杂，如果假设0吃1，1吃2，2吃0的话。可以发现a吃a+1,a被a+2吃，a和a+0是同类。

还是用一个集合表示已经确定关系的一个集体，用他们到根节点的距离表示他们分别是012中的哪种。

f[i]表示i的父节点，d[i]表示它到父节点的距离（也就是它和它父节点是什么关系）。

一开始每个点各成一个集合，它们到根节点（自己）的距离为0，意思是他们在这个集合中都是A类。

当输入的两个数(a,b)属于同一集合时，直接判断。

否则，就需要合并两个集合，先算出它们到根节点的距离来判断它们分别是自己集合中的属于哪一类，然后根据这个和目前输入的关系来计算出他们的父亲节点之间是什么关系，改变d[a的根](它本来肯定是0）。

注意：不但需要做f数组的路径压缩，同时d数组也需要同时路径压缩；i到根节点的距离是路上各个d的累加，最后mod 3才是i属于哪类。】

点击查看代码

扩充成f[3*n]，水题一道

#include

#include

#include

#include

using namespace std;

const int N=50005,K=100005;

int n,k,ans;

int f[N*3];

int find(int x)

{

if(f[x]==x) return f[x];

else return f[x]=find(f[x]);

}

void get(int p,int q)

{

int fp=find(p);

int fq=find(q);

f[fp]=fq;

}

int main()

{

int i,j;

int d,x,y;

scanf("%d%d",&n,&k);

for(i=1;in) {ans++;continue;}

bool p=true;

if(d==1)

{

if(find(x+n)==find(y)) {p=false;ans++;}

else if(find(x+2*n)==find(y)) {p=false;ans++;}

if(p)

{

get(x,y);

get(x+n,y+n);

get(x+2*n,y+2*n);

}

}

else if(d==2)

{

if(find(x)==find(y)){p=false;ans++;}

else if(find(x+2*n)==find(y)) {p=false;ans++;}

if(p)

{

get(x+n,y);

get(x+2*n,y+n);

get(x,y+2*n);

}

}

}

printf("%d\n",ans);

return 0;

}

我是这样想的，我们可以增设两个虚拟的影子（就是把n扩大到150000）把关系表达成这样：

1.如果father(x)=father(y)那么,它们同类(包括(x+n,y+n),(x+2n,y+2n));

2.类似的,如果(x+n,y)或者(x+2n,y+n),即则表示x吃y;

3.2的反面就是x被y吃;

所以程序如下:

program P1531;

var

f:array[1..150000]of longint;

i,D,n,k,x,y,ans:longint;

p:boolean;

function fa(x:longint):longint;

begin

if f[x]x then f[x]:=fa(f[x]);

exit(f[x]);

end;

procedure union(x,y:longint);

var

rx,ry:longint;

begin

rx:=fa(x);

ry:=fa(y);

if rxry then f[rx]:=ry;

end;

begin

readln(n,k);

for i:=1 to 3*n do f[i]:=i;

for i:=1 to k do begin

readln(D,x,y);

if (x>n)or(y>n) then begin inc(ans); continue; end;

if (D=2)and(x=y)then begin inc(ans); continue; end;

case D of

1:begin

p:=true;

if fa(x+n)=fa(y) then p:=false;

if fa(x+2*n)=fa(y) then p:=false;

if p then begin

union(x,y);

union(x+n,y+n);

union(x+2*n,y+2*n);

end

else inc(ans);

end;

2:begin

p:=true;

if fa(x)=fa(y) then p:=false;

if fa(x+2*n)=fa(y)then p:=false;

if p then begin

union(x+n,y);

union(x,y+2*n);

union(x+2*n,y+n);

end

else inc(ans);

end;

end;

end;

writeln(ans);

end.

并查集。。维护相对的类型就可以了。。

记录号 Flag 得分 记录信息 环境 评测机 程序提交时间

R1740752 Accepted 100 From song19931218－

　 P1531 FPC Vag 6K 2009-11-11 18:53:18

From JackDavid127

食物链 全国青少年信息学奥林匹克竞赛 (NOI) 竞赛原题

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

囧

在小错误上纠结了N长的时间，如果考试的时候也是这样的话。。。。。。。

通过AC此题学会了一种重要的并查集方法--》加权并查集

路径压缩时一定要细心。

搞清楚压缩路径和更新标记值的顺序

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

A>B>C>A>B>C>……

X与FA[X]关系值的本质是在此不等式中FA[X]的种类是在X的种类之后的第几个

1说明X吃FA[X]

2说明FA[X]吃X

所以FIND的时候累加关系值MOD 3就行了

ORZ各位独自思考出来的大牛！

我是题解参考过来的.......

有点置换群的影子...

晕到了................

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

并查集 + 比较巧妙的路径压缩 + 细心 = AC

我曰 并查集太需要注意细节了……

看了下题解发现这题有好多做法..

我的想法是这样的：类似party的做法，先分连通块，然后每个连通快随便取个点当成A，然后这个连通块的每个点就被确定下来了。然后维护这些集合即可。

爽，冰茶

LowSars - 轻量级OI奇妙的评测系统

Copyright 2007-2008 Lsz (oldherl@gmail.com)

开始测试 Hakkinen

正在编译 Hakkinen.eat ...成功

正在测试 Hakkinen.eat.1(eat1.in)... 正确 0.003秒 得分: 10

正在测试 Hakkinen.eat.2(eat2.in)... 正确 0.003秒 得分: 10

正在测试 Hakkinen.eat.3(eat3.in)... 正确 0.003秒 得分: 10

正在测试 Hakkinen.eat.4(eat4.in)... 正确 0.006秒 得分: 10

正在测试 Hakkinen.eat.5(eat5.in)... 正确 0.008秒 得分: 10

正在测试 Hakkinen.eat.6(eat6.in)... 正确 0.011秒 得分: 10

正在测试 Hakkinen.eat.7(eat7.in)... 正确 0.044秒 得分: 10

正在测试 Hakkinen.eat.8(eat8.in)... 正确 0.070秒 得分: 10

正在测试 Hakkinen.eat.9(eat9.in)... 正确 0.081秒 得分: 10

正在测试 Hakkinen.eat.10(eat10.in)... 正确 0.060秒 得分: 10

Hakkinen.eat 的总分: 100

Hakkinen 的总分: 100

评测结束时间: 2009年 08月 20日 星期四 16:06:39 CST

经过不断地30，不断地改，终于

Accepte!