拓扑排序，bitset~[JSOI2015]最小表示
2021-04-21 06:27
阅读：607
标签：规则 algorithm stream 表示 == return 最大 pac mes 传送门 题意：在有向无环图中删尽可能多的边，使图连通性不变，输出最大数量。 题解：写这题主要就是学一下bitset的用法，首先如果一个x到y的边可以删的话，说明从x到y有别的路可以走，从此还可以想到解此题的一个关键，如y可以到z，然后x连着y与z，我先让x和y连起来，则一次完成了x与y连通与z连通的任务，那么这个时候x到z就是条费边了，可加入答案，所以我们要将点的边进行排序，规则就是拓扑排序靠后的点排在后面，之后就是怎么记录y连着z，还有判断x到z是费边时怎么记录x已经与z连接起来了，这里我们用bitset去记录，这里就说几个关键的操作，bitset[x] [y]=1说明x已连接上y，bitset[x]|=bitset[y] 的意思是将y连接到的其他点也加入x。 总结一下，先用拓扑排序列出搜点的顺序，再从无出点的点（逆序）开始，往前加边，同时对边排序。 拓扑排序，bitset~[JSOI2015]最小表示 标签：规则 algorithm stream 表示 == return 最大 pac mes 原文地址：https://www.cnblogs.com/whitelily/p/13282149.html拓扑排序，bitset~[JSOI2015]最小表示
#include
评论
亲，登录后才可以留言！