POJ3041 Asteroids(二分图)

题意：

空间中有很多颗小行星，飞船要每次能清空同一行或同一列上的所有小行星，问最少要几次能将所有小行星清除。

要点：

将小行星的行作为u，列作为v建图，就是一个最小点覆盖集的裸题，最小点覆盖集=最大匹配数，直接套个模板即可。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int map[505][505], used[505], girl[505];
int n, k;bool find(int x)
{int i;for (i = 1; i <= n; i++){if (map[x][i] && !used[i]){used[i] = 1;if (girl[i] == -1 || find(girl[i])){girl[i] = x;return true;}}}return false;
}int main()
{int i, x, y;while (scanf("%d%d", &n, &k) != EOF){memset(map, 0, sizeof(map));memset(girl, -1, sizeof(girl));while (k--){scanf("%d%d", &x, &y);map[x][y] = 1;}int ans = 0;for (i = 1; i <= n; i++){memset(used, 0, sizeof(used));if (find(i)) ans++;}printf("%d\n", ans);}return 0;
}