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。那最大独立集就是=攻击格子数+既不攻击也不被攻击的格子的数目（当然最大是要放的）。
评论