讨论 / 食物链AC代码
席一鸣 2014-10-15 20:27:23
点我顶贴 收藏 删除
#include<iostream>

using namespace std;

int f[501000]={0},l[501000]={0},t[501000]={0};

int g(int x)

{

int i=x,j,k;

for(;f[i];i=f[i]);

for(j=x;f[j];k=f[j],f[j]=i,j=k);

return i;

}

int m(int x,int y)

{

if(!x)

return y;

if(!y)

return x;

return f[y]=x;

}

main()

{

int a,b,c,n,k,s=0,d,x,y,u,v;

cin>>n>>k;

while(k--)

{

cin>>d>>x>>y;

if(x>n||y>n)

{

s++;

continue;

}

u=g(x);

v=g(y);

if(d==1)

{

if(u==v)

continue;

if(l[u]==v||t[u]==v)

{

s++;

continue;

}

a=m(u,v);

b=m(l[u],l[v]);

c=m(t[u],t[v]);

t[a]=c;

t[c]=b;

t[b]=a;

l[a]=b;

l[b]=c;

l[c]=a;

}

else

{

if(t[u]==v)

continue;

if(u==v||l[u]==v)

{

s++;

continue;

}

a=m(u,l[v]);

b=m(t[u],v);

c=m(l[u],t[v]);

t[a]=b;

t[b]=c;

t[c]=a;

l[a]=c;

l[c]=b;

l[b]=a;

}

}

cout<<s;

}

#1 zjt2016@2016-03-13 16:25:44
回复 删除
var

f,r:array[0..50001]of longint;//f[i]表示节点i的祖先的序号,r[i]表示i与他的祖先的关系

n,k,i,ans:longint;

function find(x:longint):longint;//找到祖先,路径压缩,但是路径压缩时,要把关系转换一下

var

qian:longint;

begin

if f[x]=x then exit(x);

qian:=f[x];//这是x上次的祖先

f[x]:=find(f[x]);

r[x]:=(r[qian]+r[x])mod 3;//用他和他上次的祖先的关系and他上次的祖先和现在的祖先的关系推出现在他和他现在的祖先的关系

exit(f[x]);

end;

procedure hebing(x,y,z:longint);

var

fx,fy:longint;

begin

fx:=find(x);

fy:=find(y);

f[fy]:=fx;

r[fy]:=(2+z+r[x]-r[y]) mod 3;//推出fy与fx的关系

end;

procedure main;

var

x,y,z,fx,fy:longint;

begin

read(z,x,y);

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

if (x=y)and(z=2) then begin inc(ans); exit; end;

fx:=find(x);

fy:=find(y);

if fx<>fy then hebing(x,y,z);

if (fx=fy)and(((r[x]-r[y]+2+z)mod 3)<>0) then begin inc(ans); exit; end;

end;

begin

read(n,k);

for i:=1 to n do

f[i]:=i;

for i:=1 to k do

main;

write(ans);

end.

查看更多回复
提交回复