传送门
题意：
给一个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
上一篇：[luoguP3178] [HAOI2015]树上操作（dfs序 + 线段树 || 树链剖分）
下一篇：[luoguP1169] [ZJOI2007]棋盘制作（单调栈）
二分图 匈牙利算法 最小点覆盖
