题目内容
链接： POJ3041
算法详解
二分图相关知识
wiki百科已经写得挺详细了，主要讲一下二分图求最大匹配的关键定理及其证明：
Berge定理
图G的一个匹配M是最大匹配的充要条件是图G不存在M的增广路。
证明： 假设存在v0v1v2...vn为增广路（n一定为奇数，起点终点分别在两个集合）。
那么根据交错出现的定义：v0v1不属于M，v1v2属于M。该路径上存在n/2+1条路径不属于M，而n/2条路径属于M。
那么只需要，将n/2原本属于M的边剔除，n/2+1条不属于M的边加入M，M的匹配数就可以加1。
所以，如果存在增广路，就可以通过增广路与M的异或操作，使得M的匹配数加1，说明存在增广路一定不是最大匹配。
匈牙利算法
注意，二分图增广路的定义！每一个字都看清楚！M是图G的一个匹配，存在一个在M和E(G)/M 交错出现 的路径，该路径起点和终点都是非饱和点（没有对象的点），则该路径为M的一条增广路。
之前第一次自己手写实现匈牙利算法的时候，就没有注意到交错出现 这个条件，结果花费了很多时间在DFS寻找增广路的编码上面。
交错出现 有隐含含义：
- 这个路径起点终点一定在两个不同的集合
题解
说实话，能想到这道题用二分图解决的人，确实得有一定的积累才可以。要不是这道题被分到二分图下面，我也意识不到可以用二分图做。(:з」∠)
每一行的行号是一个集合，每一列的列号是一个集合，而地图中每一个行星都代表从行集合到列集合的一条边。我们的目的就是把这些边都给消除。
那为什么二分图的最大匹配数就是最小消除行星的数量呢 ？
我们先举一个具体的例子，假设地图上行星的分布是这样的：
X.X
.X.
.X.
很容易看出来，最少从第0行，第1列射线就可以了。我们来看一下这个地图的二分图构造：
graph LR
A0 --> B0
A0 --> B2
A1 --> B1
A2 --> B1
在该二分图中，A0连接着B0和B2，往A0（就是第0行）射一道激光，就可以消除与A0连接的所有边。往B1射一道激光，就可以消除B0相连的所有边。
其实就是，找最少的点，使得这些点与所有边相邻。（最小点覆盖）
而Hall定理 说：
|最小点覆盖| = |最大匹配|
于是用匈牙利算法求最大匹配，便可AC该题。
编码注意点
核心代码
核心代码为从u点出发寻找增广路并进行异或操作的代码，如下所示，关键点在代码重要已有注释。
// 匈牙利算法
bool find(int u){
// 重要！不加vis你会无限递归
if(vis[u]) return false;
vis[u] = 1;
// 日常操作，找到一条出去的路
for(int i = 1;i <= N;i++){
if(G[u][i]){
// 重要！存在一条增广路
// 很巧妙地将交错出现的条件满足
if(result[i] == 0 || find(result[i])){
// 重要！异或操作
result[i] = u;
// true代表是非饱和点
return true;
}
}
}
return false;
}
源代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 510
#define rep(i,N) for(int i = 0;i < N;i++)
// N -> N*N Square
// M -> M asteriods
int N,M;
// G[x][y]: x -> row , y -> col
// notice: x >= 1 , y >= 1
int G[maxn][maxn];
int result[maxn];
int vis[maxn];
// 匈牙利算法
bool find(int u){
if(vis[u]) return false;
vis[u] = 1;
// find a way out
for(int i = 1;i <= N;i++){
if(G[u][i]){
// 存在一条增广路
if(result[i] == 0 || find(result[i])){
result[i] = u;
return true;
}
}
}
return false;
}
int getShoot(){
memset(result,0,sizeof(result));
int count = 0;
for(int i = 1;i <= N;i++){
memset(vis,0,sizeof(vis));
if(find(i)){
count++;
}
}
return count;
}
int main(){
while(scanf("%d%d",&N,&M) != EOF){
int x,y;
memset(G,0,sizeof(G));
rep(i,M){
scanf("%d%d",&x,&y);
G[x][y] = 1;
}
printf("%d\n",getShoot());
}
}
