題干：

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).

題目大意：

在N*N的0和1組成的格子，一次操作可以將一行或一列的1全部變成0，問至少要進(jìn)行多少次操作才能將所有的1全部變成0.

解題報(bào)告：

? ? 套路建圖方式、、、裸的最小點(diǎn)覆蓋、、

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; vector<int> vv[MAX]; int nxt[MAX]; bool used[MAX]; int n,k; bool find(int x) {int up = vv[x].size();for(int i = 0; i<up; i++) {int v = vv[x][i];if(used[v] == 1) continue;used[v] = 1;if(nxt[v] == -1 || find(nxt[v])) {nxt[v] = x;return 1;}}return 0; } int match() {int sum = 0;for(int i = 1; i<=n; i++) {memset(used,0,sizeof used);if(find(i)) sum++;}return sum; } int main() {cin>>n>>k;memset(nxt,-1,sizeof nxt);for(int i = 1; i<=k; i++) {int x,y;scanf("%d%d",&x,&y);vv[x].pb(y);}printf("%d\n",match());return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【POJ - 3041】Asteroids （二分图，最小点覆盖）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。