BZOJ 2150: 部落战争 最小路径覆盖

最小路径覆盖裸题

拆点,连边。n-最大匹配数即可。注意下不可通过的情况。

bzoj 1443: [JSOI2009]游戏Game 二分图匹配

我们先明确一个事实,棋盘上alice和bob能走到的点必定是不同的,可以染成黑白相间网格,这样子我们从二分图匹配的角度考虑。

四联通建图,然后我们二分图匹配,然后我们可以发现如果可以得到完美匹配,则bob是必胜的。因为bob走一个匹配边,alice走一个非匹配边。只要还有非匹配边可以走,就必然[……]

Read more

bzoj 4443: [Scoi2015]小凸玩矩阵 二分+二分图匹配

题解:

求第k大,我们转化成求第n-k + 1小。然后我们二分一个值。对于原始矩阵如果mp[i][j]  <= x,那么我们就在行列的二分图里把i行和j列连上。然后跑一边二分图匹配,如果不小于n-k+1,那么认为结果可以更小。

我开始一直不太确定算法正确性,你能满足n-k+1个小的[……]

Read more

bzoj 1143: [CTSC2008]祭祀river 二分图匹配 floyd求闭包

我们直接跑floyd求闭包,然后求最小路径覆盖就行了。

floyd求闭包是可以相交时候求一下。

明天 吃特色餐,板子什么还没怎么复习,写到历年水题压压惊,感觉会超常发挥(药丸?)。。

bzoj 1191: [HNOI2006]超级英雄Hero 二分图匹配

N,M写反,debug半天,身败名裂。

后来又发现没有即使break了。。题没认真读完就开始写。。。。真是zz。最开始还在想要不要二分答案什么的。。。。QAQ

飞行员配对方案问题 最大流 二分图匹配

最近考场上总是自行YY各种题是网络流然后建图浪费生命。。。。。所以走一遍网络流的常见样子。

dfs里 dis 的+1还是-1写错,死循环半小时,感觉药丸。

bzoj 1562: [NOI2009]变换序列 二分图匹配

这题仔细想一下可以发现其实要实现是个二分图匹配。怎么使二分图匹配得出的匹配字典序最小,跟之前写过的一道菜肴制作采取的贪心策略相同,我们不去考虑如何让前面小的合理,我们只需考虑让后面大的足够就可了。这样子我们只要注意一下加边顺序和循环顺序即可。注意有no answer的情况。
[crayon-5bc[……]

Read more

POJ2594 Treasure Exploratio 二分图匹配+floyd求闭包

题意为给你一张有向图,可以从很多点派出很多机器人,机器人可以一直顺着边走,问至少几个机器人才能遍历所有的点。

显然这是求最小路径覆盖,而且有可能有边相交的情况,所以我们先跑一遍floyd求闭包,然后在进行二分图匹配,最后输出点数-最大匹配即可。

注意处理多case情况
[crayon-[……]

Read more

匈牙利算法(二分图匹配)学习笔记

作用:进行二分图最大匹配

可以简单理解为,左面一列男生,右面一列女生,男生只会选择特定的几个女生中的一个在一起,问最多有几对男女可以在一起。

我们举个例子,比如a喜欢 c,d b只喜欢c,那么如果我们最初让a和c在一起,那么b就找不到人了,所以这时候我们要尝试看看a能不能换一个人在一起,[……]

Read more

2776 寻找代表元 匈牙利算法 二分图匹配

题面:给出n个社团的人员组成,每个社团选中间一人当社长,每人最多当一个社长,求最多选出几个社长

题解:匈牙利算法跑一下就可以了。