POJ 3041 Asteroids（二分图 && 匈牙利算法 && 最小点覆盖）

你的名字 2023-06-04 13:56 72阅读 0赞

嗯…

#

题目链接：http://poj.org/problem?id=3041

这道题的思想比较奇特：

把x坐标、y坐标分别看成是二分图两边的点，如果（x，y）上有行星，则将（x，y）之间连一条边，而我们要做的就是要找尽量少的点把所有的边覆盖，即为最小点覆盖问题，根据König定理：最小覆盖点数=最大匹配数，所以就可以用匈牙利算法求最大匹配了。

#

AC代码：

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include<cstdio>
  2.  2 #include<cstring>
  3.  3 #include<iostream>
  4.  4 
  5.  5 using namespace std;
  6.  6 
  7.  7 int match[505], vis[505], g[505][505], n;
  8.  8 
  9.  9 inline int dfs(int u){
  10. 10     for(int i = 1; i <= n; i++){
  11. 11         if(g[u][i] && !vis[i]){
  12. 12             vis[i] = 1;
  13. 13             if(!match[i] || dfs(match[i])){
  14. 14                 match[i] = u;
  15. 15                 return 1;
  16. 16             }
  17. 17         }
  18. 18     }
  19. 19     return 0;
  20. 20 }//匈牙利
  21. 21 
  22. 22 inline int hungary(){
  23. 23     int ans = 0;
  24. 24     for(int i = 1; i <= n; i++){
  25. 25         memset(vis, 0, sizeof(vis));
  26. 26         if(dfs(i)) ans++;
  27. 27     }
  28. 28     return ans;
  29. 29 }
  30. 30 
  31. 31 int main(){
  32. 32     int k;
  33. 33     while(~scanf("%d%d", &n, &k)){
  34. 34         for(int i = 1; i <= k; i++){
  35. 35             int r, c;
  36. 36             scanf("%d%d", &r, &c);
  37. 37             g[r][c] = 1;
  38. 38         }
  39. 39         printf("%d\n", hungary());
  40. 40     }
  41. 41     return 0;
  42. 42 }

AC代码

转载于:https://www.cnblogs.com/New-ljx/p/11415338.html

发表评论

表情：
评论列表 （有 0 条评论，72人围观）

还没有评论，来说两句吧...

相关阅读