[POJ]3041 Asteroids

Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid. 

Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a single shot.This weapon is quite expensive, so she wishes to use it sparingly.Given the location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.

这道题本质上也是二分图的最大匹配问题，建图有一点小技巧。我们把所有行看做一个节点的集合S，所有列看做另一个节点的集合S'，所有陨石看做连接S和S'里两个节点的边的话。这个图就是二分图，而题目里要我们求的就是最小点覆盖，根据Konig定理二分图的最小点覆盖等于最大匹配，所以我们直接求最大匹配即可。相关算法可以参考这篇文章，时间复杂度O(V*E)，代码如下：

	//POJ 3041
	/*
	Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid.
	Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a single shot.This weapon is quite expensive, so she wishes to use it sparingly.Given the location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.
	Input
	* Line 1: Two integers N and K, separated by a single space.
	* Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= R, C <= N) denoting the row and column coordinates of an asteroid, respectively.
	Output
	* Line 1: The integer representing the minimum number of times Bessie must shoot.
	*/
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	using namespace std;
	const int MAXN = 1005;
	int graph[MAXN][MAXN], match[MAXN], visited[MAXN];
	int N, K;
	bool dfs(int u)
	{
	if (visited[u])return false;
	visited[u] = 1;
	for (int i = N + 1; i <= 2 * N; ++i)
	{
	if (i != u && graph[u][i])
	{
	if (match[i] == -1 || dfs(match[i]))
	{
	match[u] = i;
	match[i] = u;
	return true;
	}
	}
	}
	return false;
	}
	int hungarian()
	{
	int totalMatch = 0;
	for (int i = 1; i <= N; ++i)
	{
	memset(visited, 0, sizeof(visited));
	//alternating path must start with unmatched node
	if (match[i] == -1 && dfs(i))++totalMatch;
	}
	return totalMatch;
	}
	int main() {
	while (~scanf("%d%d", &N, &K)) {
	memset(graph, 0, sizeof(graph));
	for (int i = 0; i < K; ++i)
	{
	int r, c;
	scanf("%d%d", &r, &c);
	graph[r][c + N] = 1;
	}
	fill(match, match + MAXN, -1);
	//minimum vertex cover == maximum matching
	int matches = hungarian();
	printf("%d\n", matches);
	}
	return 0;
	}

view raw POJ_3041_Asteroids.cpp hosted with ❤ by GitHub