二分图最小点覆盖
题目意思：
有 n * n 的矩阵， 有k个小行星， 有位美女开飞船，开一枪可以消灭一行或者一列的
小行星。问，最少开多少枪， 可以消灭所以的小行星。
本题要点：
1、左部节点： n个横坐标
右部节点：n个纵坐标
n <= 500, 用邻接矩阵来存图
2、 最小点覆盖数定义：
就是对于一个图，选取最少数量的点S，使得对于所有的边，都至少有一端点是S中的点。
该题目中，小行星的坐标 (x, y) 转化为 二分图 左部的点 x 连上 右部的点y的一条边。
求出最小点覆盖数 的 s个点后， 假如有一点 w, 如果w 点属于左部，就把第w行 的小行星全部划掉
如果w 点属于右部，就把第w列的小行星全部划掉
3、定理：最小点覆盖数 = 最大匹配数， 所以此题转化成求最大匹配数。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 510;
int a[MaxN][MaxN], match[MaxN];
int n, k;
bool vis[MaxN];bool dfs(int x)
{
for(int y = 1; y <= n; ++y){
if(!a[x][y] || vis[y])continue;vis[y] = true;if(!match[y] || dfs(match[y])){
match[y] = x;return true;}}return false;
}int main()
{
int x, y;scanf("%d%d", &n, &k);while(k--){
scanf("%d%d", &x, &y);a[x][y] = 1;}int ans = 0;for(int i = 1; i <= n; ++i){
memset(vis, false, sizeof vis);if(dfs(i))++ans;}printf("%d\n", ans);return 0;
}/* 3 4 1 1 1 3 2 2 3 2 *//* 2 */