本文主要是介绍POJ3041 Asteroids(二分图)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
空间中有很多颗小行星，飞船要每次能清空同一行或同一列上的所有小行星，问最少要几次能将所有小行星清除。
要点：
将小行星的行作为u，列作为v建图，就是一个最小点覆盖集的裸题，最小点覆盖集=最大匹配数，直接套个模板即可。
| 15480774 | Seasonal | 3041 | Accepted | 1164K | 32MS | C++ | 665B | 2016-05-08 10:16:33 |
#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;
}这篇关于POJ3041 Asteroids(二分图)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
