POJ 3041-Asteroids（二分图最小顶点覆盖）
Asteroids
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 23625 Accepted: 12824
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).
Source
USACO 2005 November Gold
题目的大致意思是：太空中有一个N*N的矩形，里面分布着小行星（陨石），这个矩形里面有小行星，也有空格。现在主人公有个强力武器（激光炮），能够一次击碎一行或者一列的小行星。问如果主人公要把矩形中所有小行星击碎，最少需要攻击多少次。
这一道题目可以用二分图匹配来做，求得是最小点覆盖。
我们把行作为点集X，把列作为点集Y，如果在（a,b）位置有个小行星，那么我们把a和b之间连接一条边。
如此下来，就形成了一个二分图，图中X和Y集合中有多干条线连。
现在这里的每一条线段，都代表我们要消灭的目标，最后我们要把所有的线段抹去。
现在集合X和集合Y中的点就是我们可以选择的位置，我们选择其中一个，就会把与之相连的所有线段抹去。
现在我们只要尽可能选择少的点能达到目的就可以了
这个问题就是最小点覆盖问题。
有一个很重要的定理，最小覆盖数=二分图最大匹配数
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 23625 Accepted: 12824
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).
Source
USACO 2005 November Gold
题目的大致意思是：太空中有一个N*N的矩形，里面分布着小行星（陨石），这个矩形里面有小行星，也有空格。现在主人公有个强力武器（激光炮），能够一次击碎一行或者一列的小行星。问如果主人公要把矩形中所有小行星击碎，最少需要攻击多少次。
这一道题目可以用二分图匹配来做，求得是最小点覆盖。
我们把行作为点集X，把列作为点集Y，如果在（a,b）位置有个小行星，那么我们把a和b之间连接一条边。
如此下来，就形成了一个二分图，图中X和Y集合中有多干条线连。
现在这里的每一条线段，都代表我们要消灭的目标，最后我们要把所有的线段抹去。
现在集合X和集合Y中的点就是我们可以选择的位置，我们选择其中一个，就会把与之相连的所有线段抹去。
现在我们只要尽可能选择少的点能达到目的就可以了
这个问题就是最小点覆盖问题。
有一个很重要的定理，最小覆盖数=二分图最大匹配数
这和另外一道题目有异曲同工之妙HDU2119 点我传送 (๑ •̀ㅂ•́) ✧
#include<iostream>
#include<cstdio>
#include<cstring>
#include<functional>
#include<algorithm>
using namespace std;
int n,m,ans;
int vis[10005];
int cx[10005],cy[10005];
int e[10005][10005];
int path(int u)
{
for(int v=1;v<=n;v++)
{
if(e[u][v]&&!vis[v])
{
vis[v]=1;
if(cy[v]==-1||path(cy[v]))
{
cy[v]=u;
return 1;
}
}
}
return 0;
}
int MaxMatch()
{
int res=0;
memset(cy,-1,sizeof(cy));
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
res+=path(i);
}
return res;
}
int main()
{
int i,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);//建图过程
e[a][b]=1;//该行该列有目标就连接一条边
}
ans=MaxMatch();//求二分图最大匹配
printf("%d\n",ans);
}
}
投递柠檬微趣等公司10个岗位 >