【网络流】基础二分图的最大匹配问题

        标题已经说了，所以有基础的牛们就别想在这篇博客里看到什么有价值的东西。这里的解法是最基础的。

        二分图是一种可以把图中的点分为两个不同的集合，且同一集合中不存在任意两个有边联通的点（就算是单向边也不行）的图。判断是否存在二分图有一个小技巧，如果有奇数条边的环，那么一定不存在二分图（相信可以自己想通）。至于最大匹配，就是选出尽量多的边，任意一个点只能与最多一条选中的的边相连。可以参照下面的图（a）。

        二分图的最大匹配问题，与另一个同为网络流问题的最大流问题，都有一个“最大”，那么这之间是否有什么关系呢？答案是，真的有！那么现在先来了解一下有关最大流问题的的一些知识：https://blog.csdn.net/weixin_41811117/article/details/79677054。链接里的最大流用的也是基本解法。至于网络流是什么？也在链接里。

        之前说过二分图最大匹配与最大流有点关系，其实思索一下就会发现，人为主动的在图中添加一个s点与一个t点，然后将左边的点都与s点建立一条权值为1的边，右边的点都与t点建立一条权值为1的边，且所有边都改成从左集合到右集合的有向边，原本图（a）的二分图这就成了图（b），一道经典的最大流问题。

        

       至于代码什么的就算了吧（懒癌又发作了）。

        附上一道二分图匹配的模板题：Poj3041 http://poj.org/problem?id=3041

        题目大意（大部分翻译来自google，所以看不懂中文是正常的）：

小行星

时间限制： 1000MS		内存限制： 65536K
提交总数： 25001		通过： 13523

描述

贝茜希望通过一个N×N网格（1 <= N <= 500）形状的危险小行星带来驾驶她的飞船。网格包含K个小行星（1 <= K <= 10,000），它们位于网格的格点处。 

幸运的是，贝茜拥有一个强大的武器，可以消除任意一行或一列中的所有小行星。这种武器非常昂贵，所以她希望少用一些。给定所有小行星的位置，输出贝茜需要射击以消除所有小行星的最少射击次数。

输入

*第1行：两个整数N和K，由一个空格隔开。 
*第2行... K + 1行：每行包含两个空格分隔的整数R和C（1 <= R，C <= N），分别表示小行星的行坐标和列坐标。

产量

*第1行：表示贝茜必须射击的最少次数的整数。

示例输入

3 4
1 1
1 3
2 2
3 2

示例输出

2

暗示

输入详细信息： 
下图表示数据，其中“X”是小行星和“.”是空的格子： 
X.X 
.X. 
.X.  

输出细节： 
贝西可能在第1排开火，破坏（1,1）和（1,3）处的小行星，然后她可能击落第2列以破坏（2,2）和（3,2）处的小行星。 

【题解】

        我说过是模板题了。。。

感谢《算法竞赛_入门经典》的图