编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

三个集合分别表示 X的同类集合 吃X的集合 X吃的集合

经典的并查集里

编译通过...

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

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

├ 测试数据 03：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

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

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

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

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

Unaccepted 有效得分：70 有效耗时：128ms

...

后三组是极限数据吧

...

一直自信地以为-1和2 计算机会认为它们同余...

以真话作为集合的并查集。。。

getfather（a）getfather（b）那么必然为真话就进行集合合并操作

getfather（a）=getfather（b）那么就通过比较（a和getfather（a）的关系）（b和getfather（b）的关系）得出a和b的关系。。从而判断真话还是假话。。。

Const Maxn=50001;

fx1:array[1..3,1..3] of integer=((1,2,3),(2,3,1),(3,1,2));

fx2:array[1..3,1..3] of integer=((1,3,2),(2,1,3),(3,2,1));

fx3:array[1..3,1..3] of integer=((1,2,3),(3,1,2),(2,3,1));

fx4:array[1..3,1..3] of integer=((2,3,1),(1,2,3),(3,1,2));

type data=record

fa:longint;

g:integer;

end;

var

i,x,y,n,m,z,f1,f2,g1,g2,tot:longint;

a:array[1..Maxn] of data;

procedure Find(x:longint; var y,g:longint);

var

x1,x2,g1,g2:longint;

begin

y:=x; g:=1;

while a[y].fa-1 do

begin

g:=fx1[g,a[y].g];

y:=a[y].fa;

end;

x1:=x; g1:=g;

while x1y do

begin

x2:=a[x1].fa;

g2:=a[x1].g;

a[x1].fa:=y;

a[x1].g:=g1;

x1:=x2;

g1:=fx2[g1,g2];

end;

end;

begin

readln(n,m);

fillchar(a,sizeof(a),255);

for i:=1 to m do

begin

readln(z,x,y);

if (x>n) or (y>n) then inc(tot) else

begin

if z=1 then

begin

Find(x,f1,g1);

Find(y,f2,g2);

if f1=f2 then

begin

if fx2[g1,g2]z then inc(tot);

end else

begin

a[f1].fa:=f2;

a[f1].g:=fx3[g1,g2];

end;

end else

begin

if x=y then inc(tot) else

begin

Find(x,f1,g1);

Find(y,f2,g2);

if f1=f2 then

begin

if fx2[g1,g2]z then inc(tot);

end else

begin

a[f1].fa:=f2;

a[f1].g:=fx4[g1,g2];

end;

end;

end;

end;

end;

writeln(tot);

end.

阿里卤鸭~~~~~~~~

我过的第一道并查集，激动啊……

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

70 题六年

强烈谴责7.5暴力事件

program eat;

var father:array[0..50000] of word;

r:array[0..50000] of byte; //r表示与父节点之间关系，如下：0表示是同类，1表示己吃父，2表示父吃己

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

t:integer;

function find(i:word):word;

var tmp:longint;

begin

if father[i]=i then exit(i);

tmp:=father[i];

father[i]:=find(father[i]);

r[i]:=(r[tmp]+r[i]) mod 3; //!!!

exit(father[i]);

end;

procedure union(x,y,h:longint);

var a,b:longint;

begin

a:=find(x); b:=find(y);

father[a]:=b;

r[a]:=(r[y]+h-r[x]+3) mod 3; //!!!

end;

begin

readln(n,k);

for i:=1 to n do father[i]:=i;

for i:=1 to k do

begin

readln(t,x,y);

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

case t of

1: if find(x)=find(y)

then begin if r[x]r[y] then inc(ans) end

else union(x,y,0);

2: begin

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

if find(x)=find(y)

then begin if rx mod 3 then inc(ans) end

else union(x,y,1);

end;

end;

end;

writeln(ans);

end.

第60题AC....至此留念...

一次AC...好经典的并查集啊...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

AC第100题，留个纪念。

很经典的并查集题目：）

居然是0msAC的,奇怪了

哇！我是第一百个AC的哦！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

个人认为本题的最好解法不是朴素的并查集,而是加权并查集.代码十分短,而且好理解!

还可以啦

Program Noi2001_Eat_Mpq;

Const Maxn=50001;

fx1:array[1..3,1..3] of integer=((1,2,3),(2,3,1),(3,1,2));

fx2:array[1..3,1..3] of integer=((1,3,2),(2,1,3),(3,2,1));

fx3:array[1..3,1..3] of integer=((1,2,3),(3,1,2),(2,3,1));

fx4:array[1..3,1..3] of integer=((2,3,1),(1,2,3),(3,1,2));

type data=record

fa:longint;

g:integer;

end;

var

i,x,y,n,m,z,f1,f2,g1,g2,tot:longint;

a:array[1..Maxn] of data;

procedure Find(x:longint; var y,g:longint);

var

x1,x2,g1,g2:longint;

begin

y:=x; g:=1;

while a[y].fa-1 do

begin

g:=fx1[g,a[y].g];

y:=a[y].fa;

end;

x1:=x; g1:=g;

while x1y do

begin

x2:=a[x1].fa;

g2:=a[x1].g;

a[x1].fa:=y;

a[x1].g:=g1;

x1:=x2;

g1:=fx2[g1,g2];

end;

end;

begin

readln(n,m);

fillchar(a,sizeof(a),255);

for i:=1 to m do

begin

readln(z,x,y);

if (x>n) or (y>n) then inc(tot) else

begin

if z=1 then

begin

Find(x,f1,g1);

Find(y,f2,g2);

if f1=f2 then

begin

if fx2[g1,g2]z then inc(tot);

end else

begin

a[f1].fa:=f2;

a[f1].g:=fx3[g1,g2];

end;

end else

begin

if x=y then inc(tot) else

begin

Find(x,f1,g1);

Find(y,f2,g2);

if f1=f2 then

begin

if fx2[g1,g2]z then inc(tot);

end else

begin

a[f1].fa:=f2;

a[f1].g:=fx4[g1,g2];

end;

end;

end;

end;

end;

writeln(tot);

end.

我自己都没想到一次AC了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

.....................

看错题目！！！！！！！！

再次看错题目！！！！！！

太强了！！！！！！！！！

我要zro我自己了！

带权并查集！

第51个ac！

感谢vivid puppy的大力支持！