[NOI2001]食物链
这题我采用的是并查集扩展域做法,当然还有边带权的做法,但我还不会.
我们发现,所有的动物相对于每一种动物都能划分出三个集合 $:$ 同类集合,食物集合,天敌集合.
所以,把每一种动物进行扩展域,用三个并查集维护.
每次读进一个同类就判断其中一个是否在另一个的食物集合,天敌集合中即可.
如果矛盾,就统计答案,否则就把两个动物的三个集合一一合并,因为显然同类的天敌和食物都一样.
读进一个 $x$ 吃 $y$ 的捕食操作呢?
判断是否存在我吃你而你吃我的情况,这显然是矛盾的.
另一种矛盾的情况是它们已经是同类了,直接查询即可.
如果不矛盾,就合并 $x$ 的同类集合和 $y$ 的天敌集合, $x$ 的食物集合和 $y$ 的同类集合, $x$ 的食物集合和 $y$ 的食物集合.
因为既然 $x$ 吃 $y$ 那么 $x$ 的同类显然都吃 $y$ ,并且 $y$ 的同类显然都是 $x$ 的食物,根据题意还可以知道 $y$ 的食物也是 $x$ 的食物.
于是这题就做完了.
扩展域也算是并查集的套路,见过一次基本就会了.
1 |
|