POJ 1274 The Perfect Stall（二分图 && 匈牙利 && 最小点覆盖）

待我称王封你为后i 2023-06-04 13:57 23阅读 0赞

嗯...

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

一道很经典的匈牙利算法的题目：

将每只奶牛看成二分图中左边的点，将牛圈看成二分图中右边的点，如果奶牛看上某个牛圈，就将两点之间连边，然后跑一边匈牙利就行了...

AC代码：

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

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     4 
     5 using namespace std;
     6 
     7 int n, m, match[205], g[205][205], vis[205]; 
     8 
     9 inline int dfs(int u){
    10     for(int i = 1; i <= m; 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     while(~scanf("%d%d", &n, &m)){
    33         memset(g, 0, sizeof(g));
    34         memset(match, 0, sizeof(match));
    35         for(int i = 1; i <= n; i++){
    36             int s;
    37             scanf("%d", &s);
    38             for(int j = 1; j <= s; j++){
    39                 int t;
    40                 scanf("%d", &t);
    41                 g[i][t] = 1;
    42             }
    43         }
    44         printf("%d\n", hungary());
    45     }
    46     return 0;
    47 }

AC代码

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

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