POJ3041 Asteroids 二分图匹配 匈牙利算法 题目传送门 - POJ3041 题意概括 题解 代码
原文链接http://www.cnblogs.com/zhouzhendong/p/8229200.html
题意概括
有一个n*n的矩阵，有些点是障碍物。
现在每次可以炸掉某一行或者某一列的障碍物，问最少炸几次。
题解
对于点（x,y），我们建立一条x<->y+n的边，然后发现这是一个二分图。
我们只需要求最小点覆盖就可以了，因为最小点覆盖=最大匹配，所以匈牙利一波即可。
代码
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=505*2,K=10005*2;
int n,k,g[N][N],match[N],vis[N];
bool Match(int x){
for (int i=1;i<=n;i++)
if (g[x][i]&&!vis[i]){
vis[i]=1;
if (match[i]==-1||Match(match[i])){
match[i]=x;
return 1;
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&k);
memset(g,0,sizeof g);
for (int i=1,a,b;i<=k;i++)
scanf("%d%d",&a,&b),g[a][b+n]=g[b+n][a]=1;
memset(match,-1,sizeof match);
int ans=0;
for (int i=1;i<=n;i++){
memset(vis,0,sizeof vis);
if (Match(i+n))
ans++;
}
printf("%d",ans);
return 0;
}