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

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

### 嗯... ###

## ##

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

## 这道题的思想比较奇特： ##

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

# #

## AC代码： ##

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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

AC代码

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

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/2ec00c7292b347358feaba598097997b.png