做出的第一道NOI题目？（噗，还是看题解才会的…按某篇解题说的，这题就比我年轻四岁…T T 做的第一道IOI题目是USACO上的Packing Rectangles...这题比我还老！）对我等弱渣来说难度蛮大的，做了好几次并查集题目了，统统都觉得好抽象啊…这一题的难点就是，你不能直接将所有的点分为1,2,3三组，你只知道关系。边带权值的并查集也是第一次听说，一个mod 3就搞定实在太神奇…
Father数组记录祖先，Relation数组记录和祖先的距离
Relation[i]=0 表示和祖先是同类，Relation[i]=1 表示被祖先吃，Relation[i]=2表示吃祖先。
网上对于这篇的解题非常多，开成3*n数组的解法有待我研究，同时搞不清这跟向量有什么关系…最终参考比较多的是这篇文章。http://www.cnblogs.com/FreeDestiny/archive/2011/10/28/2227398.html
但是我对路径压缩，和对于Relation数组在Find函数中的更新还不是太理解，= =让我再想想。
program vijos_p1531; const maxn=50010; var relation,father:array[1..maxn] of longint; n,k,i,j,ans,t,x,y,fx,fy:longint; function find(x:longint):longint; var ff:longint; begin if father[x]=x then exit(x); ff:=find(father[x]); relation[x]:=(relation[x]+relation[father[x]]) mod 3; father[x]:=ff; exit(ff); end; begin readln(n,k); for i:=1 to n do begin father[i]:=i; relation[i]:=0; end; ans:=0; for i:=1 to k do begin readln(t,x,y); if (x>n) or (y>n) then begin inc(ans); continue; end; if t=1 then begin fx:=find(x);fy:=find(y); if (fx=fy) and (relation[x]<>relation[y]) then begin inc(ans); continue; end; if (fx<>fy) then begin father[fx]:=fy; relation[fx]:=(relation[y]-relation[x]+3) mod 3; end; end; if t=2 then begin fx:=find(x);fy:=find(y); if (fx=fy) and ((relation[x]-relation[y]+3)mod 3<>1) then begin inc(ans); continue; end; if (fx<>fy) then begin father[fx]:=fy; relation[fx]:=(relation[y]-relation[x]+4) mod 3; end; end; end; writeln(ans); end.
测试数据 #0: Accepted, time = 7 ms, mem = 1008 KiB, score = 10
测试数据 #1: Accepted, time = 7 ms, mem = 1008 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 1004 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1008 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1012 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 1008 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 1008 KiB, score = 10
测试数据 #7: Accepted, time = 62 ms, mem = 1008 KiB, score = 10
测试数据 #8: Accepted, time = 78 ms, mem = 1008 KiB, score = 10
测试数据 #9: Accepted, time = 62 ms, mem = 1008 KiB, score = 10