ShineEternal

二分图

AT刷题题解(1) BZOJ刷题题解(3) C++(1) c++小游戏汇总栏(9) codeforces刷题题解(3) ShineEternal的洛谷日报(3) SOJ刷题题解(4) 二分(1) 初赛(1) 快读(1) 未归档(314) 欢迎(1) 洛谷刷题(65) 计蒜客(1)

/ 注册

全部文章 / 二分图（共3篇）

洛谷P4304 [TJOI2013]攻击装置题解

题目链接： https://www.luogu.org/problemnew/show/P4304 分析：最大独立集最大独立集=总点数-最大匹配数独立集：点集，图中选一堆点，这堆点两两之间没有连边最大独立集：尽可能多得选点，使得其满足独立集的性质这是网络流二分图经典题目，值得...

2019-03-17

0 410

洛谷P2172 [国家集训队]部落战争题解

题目链接：https://www.luogu.org/problemnew/show/P2172 分析：不要被【国家集训队】的标签吓到，其实这题不是很难。本题可以对比P4304 [TJOI2013]攻击装置：互不攻击的网络流问题来想。这道题唯一添加的条件就是只能从上往下征战，于是我们就...

2019-03-17

0 345

洛谷P1640 [SCOI2010]连续攻击游戏题解

题目链接： https://www.luogu.org/problemnew/show/P1640 分析：这道题用二分图来解决即可.应该可以作为网络流中的模板题来食用，每一个武器有两个属性，但是只能取一个用，由此我们便可以想到与二分图挂钩。二分图匹配当中，一个点只能和一个点匹配 ...

2019-03-16

0 382