最大独立集文章列表

[luoguP3355] 骑士共存问题（二分图最大独立集）

传送门 模型 二分图最大独立集，转化为二分图最大匹配，从而用最大流解决。 实现 首先把棋盘黑白染色，使相邻格子颜色不同。 把所有可用的黑色格子看做二分图X集合中顶点，可用的白色格子看做Y集合顶点。 建...网络流,最大流,最小割,最大独立集

[luoguP2774] 方格取数问题（最大点权独立集）

传送门 引入两个概念： 最小点权覆盖集：满足每一条边的两个端点至少选一个的最小权点集。 最大点权独立集：满足每一条边的两个端点最多选一个的最大权点集。 现在对网格染色，使得相邻两点颜色不同，之后把两个...最大流,网络流,最大独立集,最小点覆盖,最小割

网络流24题

最小割=最大流 最大权闭合图=正权边之和最小割 听说这24个题很好。 开始填坑吧。 1.飞行员配对方案问题 二分图最大匹配 传送门 （好像就是个模板呀） 2.太空飞行计划问题 最大权闭合图 传送门 3...网络流,匈牙利算法,二分图,最大流,最大权完美匹配

[1143] [CTSC2008]祭祀river（最大独立集 || 偏序集最大反链）

传送门 网上说这是偏序集最大反链，然而我实在不理解。 所以我换了一个思路，先用floyd，根据点的连通性连边， 问题就转换成了找出最多的点，使任意两个点之间不连边，也就是最大独立集。 ——代码 1 #...二分图,匈牙利算法,最大独立集,Floyd

共1页/4条

---

香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化