链接：poj 3041
题意：有一个n*n的矩阵,在矩阵上有m个行星,一个武器可以消灭同一行或者同一列的星星
求最小的要用多少武器消灭所有的星星
思路：把方阵看做一个特殊的二分图（以行列分别作为两个顶点集V1、V2，其中|V1|=|V2|）
然后把每行x或者每列y看成一个点，而障碍物(x,y)可以看做连接x和y的边。按照这种思路建图，问题就转化成为选择最少的一些点(x或y)，使得从这些点与所有的边相邻，其实这就是最小点覆盖问题。
最小点覆盖数 = 最大匹配数
这样本题就转化为求最大匹配数了
-
#include<stdio.h>
-
#include<string.h>
-
int edge[550][550],n,used[550],link[550];
-
int dfs(int pos)
-
{
-
int i;
-
for(i=1;i<=n;i++)
-
if(edge[pos][i]&&!used[i]){
-
used[i]=1;
-
if(link[i]==-1||dfs(link[i])){
-
link[i]=pos;
-
return 1;
-
}
-
}
-
return 0;
-
}
-
int main()
-
{
-
int i,a,b,s,m;
-
scanf("%d%d",&n,&m);
-
memset(edge,0,sizeof(edge));
-
for(i=0;i<m;i++){
-
scanf("%d%d",&a,&b);
-
edge[a][b]=1;
-
}
-
s=0;
-
memset(link,-1,sizeof(link));
-
for(i=1;i<=n;i++){
-
memset(used,0,sizeof(used));
-
s+=dfs(i);
-
}
-
printf("%d\n",s);
-
return 0;
-
}
poj 3041 Asteroids (最小点覆盖)
原文：http://blog.csdn.net/acm_code/article/details/39852147
