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.
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
题目类型：最小点覆盖(二分图最大匹配)
算法分析：首先要对原图进行一个转化，将每行中的行星看做是在一个块中并标号，每列中的行星看做是在一个块中并标号，每个块中最多只需一个子弹就可以全部消灭行星。然后将横块和竖块中重合的块之间连线，这样原图就转化成一个等效的二分图。现在等效求解用多少点(块)来“覆盖”边，使得所有的边都被覆盖到。这样直接求解最大匹配即可
|
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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 |
/************************************************* Author :supermaker Created Time :2016/1/20 12:46:45 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 500 + 66; int xs[maxn][maxn], ys[maxn][maxn]; bool g[maxn][maxn], vis[maxn*maxn], gg[maxn][maxn]; int cx[maxn*maxn], cy[maxn*maxn], cxlen, cylen; int dfs (int u) { for (int v = 1; v <= cylen; v++) if (g[u][v] && !vis[v]) { vis[v] = true; if (cy[v] == -1 || dfs (cy[v])) { cy[v] = u; cx[u] = v; return 1; } } return 0; } int maxmatch () { int res = 0; memset (cx, -1, sizeof (cx)); memset (cy, -1, sizeof (cy)); for (int i = 1; i <= cxlen; i++) if (cx[i] == -1) { memset (vis, false, sizeof (vis)); res += dfs (i); } return res; } int main() { //CFF; //CPPFF; int n, k; while (scanf ("%d%d", &n, &k) != EOF) { memset (gg, false, sizeof (gg)); memset (g, false, sizeof (g)); memset (xs, 0, sizeof (xs)); memset (ys, 0, sizeof (ys)); for (int i = 1; i <= k; i++) { int u, v; scanf ("%d%d", &u, &v); gg[u][v] = true; } cxlen = 0; for (int i = 1; i <= n; i++) { bool is_first = true; for (int j = 1; j <= n; j++) if (gg[i][j]) { if (is_first) { is_first = false; xs[i][j] = ++cxlen; } else xs[i][j] = cxlen; } } cylen = 0; for (int i = 1; i <= n; i++) { bool is_first = true; for (int j = 1; j <= n; j++) if (gg[j][i]) { if (is_first) { is_first = false; ys[j][i] = ++cylen; } else ys[j][i] = cylen; } } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (xs[i][j]) g[xs[i][j]][ys[i][j]] = true; printf ("%d\n", maxmatch ()); } return 0; } |
- « 上一篇：poj1422
- poj1043：下一篇 »