首页 > 代码库 > [POJ3041] Asteroids（最小点覆盖-匈牙利算法）
[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 {14 to[cnt] = y;15 next[cnt] = head[x];16 head[x] = cnt++;17 }18 19 inline bool find(int u)20 {21 int i, v;22 for(i = head[u]; i != -1; i = next[i])23 {24 v = to[i];25 if(!vis[v])26 {27 vis[v] = 1;28 if(!belong[v] || find(belong[v]))29 {30 belong[v] = u;31 return 1;32 }33 }34 }35 return 0;36 }37 38 int main()39 {40 int i, x, y;41 scanf("%d %d", &n, &k);42 M(-1, head);43 for(i = 1; i <= k; i++)44 {45 scanf("%d %d", &x, &y);46 add(x, y);47 }48 for(i = 1; i <= n; i++)49 {50 M(0, vis);51 if(find(i)) ans++;52 }53 printf("%d", ans);54 return 0;55 }
[POJ3041] Asteroids（最小点覆盖-匈牙利算法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。