POJ3041-Asteroids（二分图匹配）

题目链接

http://poj.org/problem?id=3041

题意

给定一个N*N的格子，里面有K个点，每次攻击的范围为1行或1列，要求用最少的攻击次数，覆盖掉所有的点 如图所示： 选择图中的两条线

思路

每个点可以选择横着攻击或者竖着攻击两种方式，于是将所有的横着攻击和竖着攻击看做两部分点集{u}和{v}，则每个点对应着连接u中的某点和v中的某点的直线，如图所示： 则题目就变成了选择最少的顶点覆盖掉所有的边，为最小顶点覆盖，在二分图中就是二分图的最大匹配

代码

#include <iostream> #include <cstring> #include <stack> #include <vector> #include <set> #include <map> #include <cmath> #include <queue> #include <sstream> #include <iomanip> #include <fstream> #include <cstdio> #include <cstdlib> #include <climits> #include <deque> #include <bitset> #include <algorithm> using namespace std; #define PI acos(-1.0) #define LL long long #define PII pair<int, int> #define PLL pair<LL, LL> #define mp make_pair #define IN freopen("in.txt", "r", stdin) #define OUT freopen("out.txt", "wb", stdout) #define scan(x) scanf("%d", &x) #define scan2(x, y) scanf("%d%d", &x, &y) #define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z) #define sqr(x) (x) * (x) #define pr(x) cout << #x << " = " << x << endl #define lc o << 1 #define rc o << 1 | 1 #define pl() cout << endl const int maxn = 2000; const int maxm = 10005 << 1; int n, m; struct Edge { int to, next; }; Edge edges[maxm]; int head[maxn], cnt; int used[maxn], belong[maxn]; void add(int u, int v) { edges[cnt].to = v; edges[cnt].next = head[u]; head[u] = cnt++; } bool dfs(int x) { for (int i = head[x]; ~i; i = edges[i].next) { int v = edges[i].to; if (!used[v]) { used[v] = 1; if (belong[v] == -1 || dfs(belong[v])) { belong[v] = x; return true; } } } return false; } int match() { int ans = 0; memset(belong, -1, sizeof(belong)); for (int i = 1; i <= n * 2; i++) { memset(used, 0, sizeof(used)); if (dfs(i)) ans++; } return ans; } int main() { scan2(n, m); memset(head, -1, sizeof(head)); cnt = 0; for (int i = 0; i < m; i++) { int u, v; scan2(u, v); add(u, v + n); add(v + n, u); } printf("%d\n", match() / 2); return 0; }