寒江陪烟火🔥

二分匹配

acm相关(6) dp(68) RMQ(5) STL(6) 主席树(2) 二分查找(2) 分治法(3) 划分树(1) 单调队列(2) 博弈(11) 字典树(3) 字符串处理(1) 学习(1) 并查集(4) 强联通分量(3) 归并排序(1) 拓扑排序(1) 搜索(1) 数论(8) 最小生成树(3) 最短路(5) 树状数组(7) 树链剖分(4) 欧拉回路(5) 简单模版(14) 简单题(24) 线段树(13) 网络流(6)

/ 注册

全部文章 / 二分匹配（共23篇）

HDU5943 Kingdom of Obsession（思路题+二分匹配）

题意：给你两个数n,s(1e9)，问你能否使得s+1--s+n和1--n全部匹配每个数只能匹配他的因子思路：要匹配的这一段数中非重合部分最多有1个素数，也就是说n和s不能同时很大我打了1e9的素数间隔表，发现最大间距才280多。。然后索性直接当n和s都大于500的时候就输出n...

2016-10-30

0 346

HDU5806 NanoApe Loves Sequence Ⅱ（二分ortwo-pointer）

题意：求满足区间中>=m的数>=k个的区间有多少思路：记小于m的数为0，大于等于m的为1，用sum维护区间和然后我的做法是枚举右端点，二分左端点得到答案，复杂度O（nlogn） /* ****************************************...

2016-08-07

0 270

HDU5727 Necklace（环排+匈牙利）

这个题是参考网上各大聚聚的代码才写出来的，没办法我太弱了题意：给你阴阳珠子各n个，让你串成阴阳相间的串。给你m种搭配，表示某阳珠子与某阴珠子相邻时会变暗问你最少有多少阳珠子变暗思路：当时想到了可能与二分图有关，但是一直没有什么好的思路看了网上的题解才恍然大悟大概就是先...

2016-07-20

0 234

HDU3488 Tour km

/* *********************************************** Author :devil Created Time :2016/5/25 17:22:34 ********************************************...

2016-05-25

0 240

HDU2255 奔小康赚大钱（km模板题）

Description 传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容...

2016-05-25

0 221

POJ3189 Steady Cow Assignment（二分图多重匹配）

题意： N头牛M个棚，每头牛对每个棚都有喜爱顺序每个棚都有自己的容量问你怎么分配使得所有牛的喜爱程度差距最小思路： l r表示一段喜爱程度的范围建图就按l 到 r里的棚子建然后两个标移动从头到尾就可以扫出最小值了 /* ************************...

2016-05-17

0 338

POJ2112 Optimal Milking（二分图多重匹配）

题意： K个产奶机，C头奶牛，每个产奶机最多可供M头奶牛使用；并告诉了产奶机、奶牛之间的两两距离Dij(0<=i,j<K+C)。问题：如何安排使得在任何一头奶牛都有自己产奶机的条件下，奶牛到产奶机的最远距离最短？最短是多少？思路：二分图多重匹配先用floyd求最短距离 ...

2016-05-17

0 240

POJ2289 Jamie's Contact Groups（二分图多重匹配）

题意：给定一个规模为n的名单，要将名单中的人归到m个组中，给出每个人可能的分组号，需要确定一种分配方案，使得最大规模的组最小。思路：二分图多重匹配如果所到的组没满，就去那个组如果满了，就从那个组里踢出一个如果能踢出来，就把那个踢出来，把当前的放进去如果所有能到的组都踢不出...

2016-05-17

0 263

HDU3829 Cat VS Dog（最大独立集）

题意： n个小孩，每个小孩喜欢一种动物讨厌一种动物你是管理员，可以任意去掉一些动物当小孩讨厌的动物被去掉并且喜欢的动物没有被去掉时，他是开心的问最多让多少小孩开心思路：让有矛盾的小孩建边，求最大独立集即可 /* ***************************...

2016-05-17

0 248

POJ2594 Treasure Exploration（最小路径覆盖+传递闭包）

题意：派机器人去火星寻宝，给出一个无环的有向图，机器人可以降落在任何一个点上，再沿着路去其他点探索，我们的任务是计算至少派多少机器人就可以访问到所有的点。。思路：最小路径覆盖，只是点可以重复去，就需要求传递闭包，用floyd /* *******************...

2016-05-17

0 244