拓扑排序，bitset~[JSOI2015]最小表示

2021-04-21 06:27

阅读：597

标签：规则 algorithm stream 表示 == return 最大 pac mes

拓扑排序，bitset~[JSOI2015]最小表示

传送门

题意：在有向无环图中删尽可能多的边，使图连通性不变，输出最大数量。

题解：写这题主要就是学一下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。

总结一下，先用拓扑排序列出搜点的顺序，再从无出点的点（逆序）开始，往前加边，同时对边排序。

#include
#include
#include
#include
#include
#include
using namespace std;
#define pb push_back
int n,m,v,u,ru[30007],dis[30007];
vectorho[30007];
vectoredg;
queuesa;
bitsetse[30007];
bool cmp(int a,int b){
	return dis[a]=0;i--){
		lin=edg[i];
		se[lin][lin]=1;
		for(int j=0;j

拓扑排序，bitset~[JSOI2015]最小表示

标签：规则 algorithm stream 表示 == return 最大 pac mes

原文地址：https://www.cnblogs.com/whitelily/p/13282149.html

上一篇：Windows 10 Java环境变量配置

下一篇：利用Python进行Payload分离免杀

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：拓扑排序，bitset~[JSOI2015]最小表示
文章链接：http://soscw.com/index.php/essay/77477.html

亲，登录后才可以留言！

拓扑排序，bitset~[JSOI2015]最小表示

拓扑排序，bitset~[JSOI2015]最小表示

评论

热门文章

推荐文章

最新文章

置顶文章