Trancy

4月1日下午 又来看看课件刷一下二分图匹配

1.POJ1325:

题目大意就是有两台机器A,B,分别由m和n种模式,初始时都在模式0,现在有k个工作,每一个工作都可以将A设置成模式i或将B设置成模式j,但每一次更换模式时机器不得不要重启,求完成所有工作的最小重启次数输入数据的第一行有三个数据,分别代表工作数,A/B的模式数,当输入0时结束程序,接下来多行,每行的开始代表工作的序号,和完成该工作需将A/B设置的模式数,输出一个整数,代表机器最小重启次数,

分析:

之前看了一下网友的各种评论,大意是二分图匹配问题并不常见,写起来也非常简单当然是指匈牙利算法了,但很多题目只要能转换过来是非常方便的。

看到这道题,感觉说的真是太对了,完全没有想过这可以用二分图来写。

这道题主要难度是建图的问题,左边是A机器的所有模式,右边是B的,对于每一个任务,A和B连一条线,求最小点覆盖=最大匹配,每一任务相当于一条边,选择最少的模式把它覆盖完就好了??因为一个点只能与一条线相连,如果有一点多边的情况重启次数也只是1的。


二分图的最大独立集=图的点数-最小点覆盖(比较好理解)

(最小点覆盖在数值上市等于最大匹配的)

2.骑士放置

大意:求n*m的棋盘上最多能放多少个互不攻击的骑士(马)

分析:这一道题也是好妙的样子。

我们首先将棋盘进行黑白交叉染色,根据规则,攻击与被攻击的格子一定是异色的,又具备对称性,我们可以将黑左当成放置马的预选位置,白右。最大独立集就是答案。

因为一个格子可攻击到多个格子,也可以说一个格子可被多个格子攻击,那么重复的我们就不管它了,最大匹配就是(所有能攻击和所有被攻击的格子数)之和/2。那最大独立集就是=攻击格子数+既不攻击也不被攻击的格子的数目(当然最大是要放的)。

评论