| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 26141 | Accepted: 14134 |
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
* 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
Sample Input
|
1 2 3 4 5 |
3 4 1 1 1 3 2 2 3 2 |
Sample Output
|
1 |
2 |
Hint
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
思路
首先明确几个概念：
二分图：指定点可以分为两个不相交的集\(U\) 和\(V\)，其中\(U\)和\(V\)皆为独立集，使得在同一个集内的定点不相邻的图。另外还有一个有趣的等价定义：不含有「含奇数条边的环」的图。
匹配：一个任意两条边都没有公共顶点的边的集合。
最大匹配：一个图中所含匹配边数最多的匹配。
在这个题目里面把每一行每一列都看成点，然后把行与列之间的交点看成边，就转换成求的最大二分匹配的问题，然后直接套匈牙利算法模板即可。
代码
|
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 |
/* * File Name: poj3041.cpp * Author: razrLeLe * Mail: razrlele@gmail.com */ #include <vector> #include <set> #include <deque> #include <queue> #include <algorithm> #include <functional> #include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <string> #include <cstring> #include <string.h> #include <map> #include <cctype> #include <list> #include <stack> #define ll long long using namespace std; #define INF 0x3f3f3f3f #define LOCAL int N, K; const int max_n = 1500; struct Edge { int from; int to; Edge(int f, int t): from(f), to(t) {} }; vector<int> G[max_n]; vector<Edge> edges; int matching[max_n]; int check[max_n]; bool dfs(int u){ for (vector<int>::iterator i = G[u].begin(); i != G[u].end(); ++i) { int v = edges[*i].to; // cout << u << " " << v << endl; if(!check[v]) { check[v] = true; if (matching[v] == -1 || dfs(matching[v])) { matching[v] = u; matching[u] = v; return true; } } } return false; } int hungarian(){ int ans = 0; memset(matching, -1, sizeof(matching)); for (int u = 1; u <= N*2; u++) { if (matching[u] == -1) { memset(check, 0, sizeof(check)); if(dfs(u)){ ans++; } } } return ans; } int main(int argc, char ** argv) { #ifdef LOCAL freopen("/Users/razrlele/build/in.data", "r", stdin); //freopen("/Users/razrlele/build/out.data", "w", stdout); #endif cin >> N >> K; int f, t; int e_count = 0; for(int i = 0; i < K; i++) { cin >> f >> t; G[f].push_back(e_count); edges.push_back(Edge(f, t+N)); e_count++; G[t+N].push_back(e_count); edges.push_back(Edge(t+N, f)); e_count++; } cout << hungarian() << endl; return 0; } |