• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

[AcWing 240] P2024 [NOI2001]食物链


Recommended Posts

image

image

单击以查看代码#includeiostream。

使用命名空间std

const int N=5e5 10

int p[N],d[N];

int find(int x)

{

if (p[x]!=x) {

int u=find(p[x]);

d[x]=d[p[x]];

p[x]=u;

}

return p[x];

}

int main()

{

int n,k;

CINnk;

for(int I=1;I=n;I)p=I;

int RES=0;

while (k - ) {

int t,x,y;

scanf('%d %d %d ',t,x,y);

if(x n | | y n)RES;

否则{

int px=find(x),py=find(y);

if (t==1) {

if(px==py(d[x]-d[y])% 3)RES;

else if (px!=py) {

p[px]=py;

d[px]=d[y]-d[x];

}

}

否则{

if(px==py(d[x]-d[y]-1)% 3)RES;

else if (px!=py) {

p[px]=py;

d[px]=d[y]1-d[x];

}

}

}

}

cout res

返回0;

}

在维护联合集的同时,记录每个节点和根节点之间的距离。距离1表示根节点可以吃,距离2表示可以被根节点吃,距离3表示和根节点是同类。

距离的更新在find中完成。u=find(p[ x])有两个作用,一是记录根节点,二是更新p[ x]后面的节点到根节点的距离。这条语句执行后,d[ p[ x]]是p[ x]到根节点的距离;

有三种情况的res:

x n或y n,违反条件2;

t==1,X和Y属于同一个集合,但d[ x]% 3和d[ y]% 3的值不同,即(d[ x]-d[ y ])% 3!=0,那么根据距离的含义,X和Y与根节点的关系一定是不同的,从而推导出X和Y不是一类,t==1表示X和Y是一类,违反了条件1;

t==0,X和Y属于同一个集合。如果X吃Y,根据题目条件,只有A吃B,B吃C,那么C吃A,如果X想吃Y,Y需要吃根节点,根节点吃X,那么X吃Y,在这个条件下,d[ x]和d[ y]需要满足一定的条件。吃根节点意味着d[ y]% 3==1,X被根节点吃了,意味着d[ x]% 3==2,即(d[ x]-d[ y]-1)% 3==0,那么如果(D [X]-D [Y]-1)=0,肯定没有X吃Y,这与t==0相矛盾意味着X吃Y,违反了条件1;(X吃X可以看作X吃Y的特例,当y=x时,也违反了条件3)

需要合并和检查集合的两种情况:

t==1,X和Y不属于同一个集合。设X的根节点是Y的根节点的子节点,需要让d[ px]取某个值。当t==1时,X和Y是同类的。此时X和Y的距离为d[ x] d[ px],Y和Y的距离为d[ y]。两个距离% 3的值应该相同。举一个简单的例子,两个距离相等。从d[ x] d[ px]=d[ y]可以推导出d[px]=d[y]-d[x];

t==0,X和Y不属于同一个集合。设X的根节点是Y的根节点的子节点,设d[ px]取某个值。t==0时,X吃Y,此时X与Y的根节点距离为d[ x] d[ px],Y与Y的根节点距离为d[ y]。x的距离应该是% 3=2,y的距离应该是% 3=1。在一个简单的情况下,让两个距离之差为1。由d[ x] d[ px]-d[ y]=1,可以推导出d[px]=d[y]1-d[x];

Link to comment
Share on other sites