[POJ3041] Asteroids（最小点覆盖-匈牙利算法）

传送门

题意：

给一个N*N的矩阵，有些格子有障碍，要求我们消除这些障碍，问每次消除一行或一列的障碍，最少要几次。

解析：

把每一行与每一列当做二分图两边的点。

某格子有障碍，则对应行与列连边。

选出最少的点，使得所有边被覆盖。

最小点覆盖。

——代码

1 #include <cstdio> 2 #include <cstring> 3 #define M(x, a) memset(a, x, sizeof(a)) 4 5 using namespace std; 6 7 const int MAXN = 501; 8 int n, k, cnt, ans; 9 int head[MAXN], next[MAXN * MAXN], to[MAXN * MAXN], belong[MAXN]; 10 bool vis[MAXN]; 11 12 inline void add(int x, int y) 13 18 19 inline bool find(int u) 20 33 } 34 } 35 return 0; 36 } 37 38 int main() 39 48 for(i = 1; i <= n; i++) 49 53 printf("%d", ans); 54 return 0; 55 }
View Code

上一篇：[luoguP2982][USACO10FEB]慢下来Slowing down（dfs序 + 线段树）

下一篇：[HDU2196]Computer（DP）

---

二分图 最小点覆盖 匈牙利算法