首页 > 代码库 > [COCI 2013/2014 ROUND 5] ladice
[COCI 2013/2014 ROUND 5] ladice
分析:
对于一个物品,只有两个抽屉A,B可以放,那么如果能够放下,那么一定是放在其中一个,设放在A中,那么以后可以且只能将其移动到B中,所以我们建一条有向边由A指向B,这样处理下去我们会发现对于每一条有向边一定是有物品的抽屉指向没有物品的抽屉,那么我们定义一个块为之间有边的点的集合,定义块的根为块中没有出边的点,那么一个块中只有根会是空的抽屉其他的一定是有物品的抽屉,那么每一个块就可以用一个并查集维护起来,每加一个物品(即加一条边)时,对于两个端点A,B,如果有A所在的并查集的根可以放那么就将A所在的并查集的根标记为有物品,将A所在的并查集连到B的并查集的根上,如果不行就再考虑B,如果都不行,就无法放入。对于连成环的情况其实就等价于根有物品。
下面是代码:
1 #include<cstdio> 2 #define maxn 300100 3 4 int n,l,f[maxn],a,b,use[maxn]; 5 6 int find(int a) 7 { 8 int i,t=a; 9 for (;t!=f[t];t=f[t]);10 for (;a!=f[a];a=i){i=f[a];f[a]=t;}11 return t;12 }13 14 int main()15 {16 scanf("%d%d",&n,&l);17 for (int i=1;i<=l;i++) f[i]=i;18 for (int i=1;i<=n;i++)19 {20 scanf("%d%d",&a,&b);21 if (!use[find(a)])22 {23 use[f[a]]=1;24 if (f[a]!=find(b)) f[f[a]]=f[b]; //避免出现环,环等价于根无法放 25 puts("LADICA");26 }27 else if (!use[find(b)])28 {29 use[f[b]]=1;30 //a的并查集无法放,那么就没有合并的必要了 31 puts("LADICA");32 }33 else puts("SMECE");34 }35 return 0;36 }
[COCI 2013/2014 ROUND 5] ladice
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。