Asteroids

Description

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.

Sample Input

3 4
1 1
1 3
2 2
3 2

Sample Output

2

Hint

INPUT DETAILS:
The following diagram represents the data, where “X” is an asteroid and “.” is empty space:
X.X
.X.
.X.

OUTPUT DETAILS:
Bessie may fire across row 1 to destroy the asteroids at (1,1) and (1,3), and then she may fire down column 2 to destroy the asteroids at (2,2) and (3,2).
题目在意如下:
题目给出一个矩阵，上面有敌人，每个子弹可以打出一横行或者一竖行，问最少用多少子弹消灭都有敌人，如：
X.X
.X.
.X.
x表示敌人，显然用两个子弹就可以解决所有敌人。

解题思路

这题就是最小点覆盖
定义：
假如选了一个点就相当于覆盖了以它为端点的所有边，最小顶点覆盖就是选择最少的点来覆盖所有的边。
可以证明：二分图最小点覆盖数=最大匹配数。
证明： 假设最大匹配边数为M
1.M是足够的。因为如果存在边E未与顶点相连，则E可以匹配，此时不是最大匹配。 （≤m）
2.M是必须的。仅考虑构成最大匹配的M条边，他们两两无公共点，所以需要M个顶点覆盖他们。（≥m）
所以只有=m

那么这么一化简，这题就成了一道最大匹配模板题
可参考人员分配（最大匹配）两题大同小异

AC代码

邻接矩阵

邻接矩阵就很简单了，用一个a来存相连的边，再套用匈牙利算法就AC了
因为人员分配中有详细注释，我这里就不注释了

#include<iostream>
#include<cstdio>
using namespace std;
int n,s,x,y,answer,cover[105],father[105],a[105][105];
bool dfs(int x)
{
   
	if(x==0)return true;
	for(int i=1;i<=n;i++)
	 if(a[x][i]==1&&cover[i]==0)
	 {
   
	 	cover[i]=1;
	 	int sum=father[i];
		father[i]=x;
	 	if(sum==0||dfs(sum))return true;
	 	father[i]=sum;
	 }
	return false;
}
int main()
{
   
	scanf("%d%d",&n,&s);
	for(int i=1;i<=s;i++)
	{
   
		scanf("%d%d",&x,&y);
		a[x][y]=1;
	}
	for(int i=1;i<=n;i++)
	{
   
		memset(cover,0,sizeof(cover));
		dfs(i);
	}
	for(int i=1;i<=n;i++)
	 if(father[i]!=0)answer++;
	printf("%d",answer);
	return 0; 
}

邻接表

邻接表就和邻接矩阵的方法差不多，同样用一个a来存储相连的边，只不过存储的方式不同，再套用匈牙利算法就AC了
因为人员分配中有详细注释，我这里就不注释了

#include<iostream>
#include<cstdio>
using namespace std;
int n,s,x,y,tot,answer,head[105],cover[105],father[105];
struct node
{
   
	int to,next;
}a[10005];
void add(int x,int y)
{
   
	a[++tot]=(node){
   y,head[x]};
	head[x]=tot;
}
bool dfs(int x)
{
   
	if(x==0)return true;
	for(int i=head[x];i;i=a[i].next)
	 if(cover[a[i].to]==0)
	 {
   
	 	cover[a[i].to]=1;
	 	int sum=father[a[i].to];
		father[a[i].to]=x;
	 	if(sum==0||dfs(sum))return true;
	 	father[a[i].to]=sum;
	 }
	return false;
}
int main()
{
   
	scanf("%d%d",&n,&s);
	for(int i=1;i<=s;i++)
	{
   
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++)
	{
   
		memset(cover,0,sizeof(cover));
		dfs(i);
	}
	for(int i=1;i<=n;i++)
	 if(father[i]!=0)answer++;
	printf("%d",answer);
	return 0; 
}

谢谢