Category Archives: 匹配问题

FZU 2194 星系碰撞 (二分染色)

给出n个坐标,如果两个坐标距离>5说明是同一个系的,求同一个系最大能有多少点。 其实就是一个最大独立集的 …

HDU 4687 Boke and Tsukkomi (带花树)

额。

 

HDU 3488 Tour (二分图完美匹配)

一个有向图,使其分成若干个环,这些还包含了所有点,但是每个点仅能属于一个还,求这些环边的最小权和 对于有向图, …

KM算法

二分图带权匹配

 

多重匹配

 

HDU 3829 Cat VS Dog (最大独立集)

动物园有不同种类的猫和狗,有p个小朋友去参观动物园,每个小朋友都有喜欢或讨厌的猫或狗,现在如何移除某些动物使得 …

POJ 2594 Treasure Exploration (最小路径覆盖)

机器人在图上走,用最少的机器人走遍全图,图是单向无环图。 最小路径覆盖,存在路径之间有公共点,所以先对原图求一 …

二分图的一些总结

关于不同图求最大匹配的处理方法: 1.有向图,将图拆点变成入点和出点,对于某个临边u->v, 那么 u0 …

二分图 — Hopcroft-Karp 算法

为了降低时间复杂度,可以在增广匹配集合M时,每次寻找多条增广路径。这样就可以进一步降低时间复杂度,可以证明,算 …

HDU 1281 棋盘游戏(二分匹配,找增光路)

在一个n*m的棋盘上,每行每列只能放一个棋子,有些各自不能放棋子,最大能放的棋子数是mt,问有多少个位置是一定 …