P7368 [USACO05NOV]Asteroids G ( 二分图最小点覆盖 )

题目描述

贝茜想在 $N\times N$ 的网格中驾驶她的宇宙飞船。网格中有 $K$ 个小行星。要使驾驶过程愉快，就必须把这些小行星全部消除。

贝茜有一个武器，可以以一个单位代价消除一行或一列的全部小行星。贝茜想问你，要把所有小行星都消除的最小代价是多少。

输入格式

第一行两个整数 $N,K$。

接下来 $K$ 行，每行输入 $x_i,y_i$，表示第 $i$ 个小行星在网格的坐标。

输出格式

一行一个整数，表示把所有小行星消除的最小代价。

样例 #1

样例输入 #1

3 4
1 1
1 3
2 2
3 2
1
2
3
4
5

样例输出 #1

2
1

提示

样例解释：

样例的图为（X 为小行星）：

X.X
.X.
.X.
1
2
3

贝茜可以分别消除第一行和第二列的小行星。

---

数据范围：

对于 $100\%$ 的数据，$1\le N\le 500$，$1\le K\le N\times N$。

思路：

将一个点的坐标抽象为一条边，具体来说就是 x -> y的一条边。
此时，问题就变成了最小点覆盖问题，即如何用最小的点覆盖所有的边。
由于最小点覆盖=最大匹配，故直接匈牙利算法跑就行。

代码：

#include
#include
using namespace std;
const int N=1e6+10;
int st[N],match[N];
int g[1005][1005];
int n,k;
bool find(int u)
{
	for(int i=1;i<=n;i++)
	{
		if(st[i])
		{
			continue;
		}
		if(g[u][i])
		{
			st[i]=true;
			if(match[i] == -1 || find(match[i]))
			{
				match[i]=u;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	memset(match,-1,sizeof match);
	cin>>n>>k;
	for(int i=0;i<k;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x][y]=1;
	}
	int res=0;
	for(int i=1;i<=n;i++)
	{
		memset(st,false,sizeof st);
		if(find(i))
		{
			res++;
		}
	}
	cout<<res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48