题目链接：?id=3041
题意：n*n矩阵上有行星，每次只能在一行或一列放一发子弹，消灭本行或列的所有行星，求消灭所有行星的最小消耗子弹数目。
解法：二分图，行为一个顶点集，列为另一顶点集。题目转化成为选择最少的一些点(x或y)，使得从这些点与所有的边相邻，，其实这就是最小点覆盖问题。
代码：
;int p[510][510];int n;int k;int a,b;int book[510];int match[510];bool dfs(int u){for (int i = 1; i <= n; i++){if (book[i] == 0 && p[u][i] == 1){book[i] = 1;if (match[i] == 0 || dfs(match[i])){match[i] = u;return true;}}}return false;}int main(){while (scanf(“%d%d”,&n,&k)!=EOF){memset(p,0,sizeof(p));memset(match,0,sizeof(match));while(k–){scanf(“%d%d”,&a,&b);p[a][b] = 1;}int ans = 0;for(int i=1;i<=n;i++){memset(book, 0, sizeof(book));if (dfs(i))ans++;}printf(“%d\n”,ans);}return 0;}
这种精神使人能在旅行中和大自然更加接近，
