[华为机试]素数伴侣【匈牙利算法：最大二分匹配】

迈不过友情╰ 2023-01-17 07:50 107阅读 0赞

[题目链接][Link 1]

--------------------

[百度百科][Link 2]

二分图：将节点分成两组，A和B，边都是横跨在两组之间的，组内是没有边的相连的

判断方法，[染色法][Link 3]

[匹配][Link 4]:边的集合，任意两个边都没有公共的节点

最大匹配：找出匹配的边集合最大

[匈牙利算法][Link 2]

> 交错路  
> 增广路径  
> 需要证明的是没有增广路径的时候就是最大匹配了

知乎一篇写的很不错的文章  
[https://zhuanlan.zhihu.com/p/96229700][https_zhuanlan.zhihu.com_p_96229700]

看了这个算法，用了男女生匹配的方式进行讲解，其实match函数就是在找增广路径  
增广路径要以没有匹配的节点开始，  
所以match(i)的时候，i前面的要么是已经match了  
要么就是考虑过了，没法match  
如果match(i) 返回是真，那么就是说还存在增广路径  
否则就是考虑到i的最大匹配了

正常来说，我们应该考虑所有的情况，最后挑一个最大的匹配  
这里复杂度变低的原因就是，算法只从前到后运行一次  
增广路径不可能往前找，满足贪心的性质，所以复杂度就低了

--------------------

看懂题解之后 耗时23min

#include <iostream>
    #include <stdio.h>
    #include <math.h>
    #include <algorithm>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    bool isp(int n){ 
        int s = sqrt(n);
        for(int i=2;i<=s;i++){ 
            if(n%i==0){ 
                return false;
            }
        }
        return true;
    }
    
    int b[100];
    int g[100];
    bool l[100][100];
    int v[100];
    int bc;
    int gc;
    int p[100];
    
    bool findg(int bi){ 
        
        for(int gi=0;gi<gc;gi++){ 
            if( l[bi][gi] && v[gi]==0){ 
                v[gi] = 1;
                if( p[gi]==-1 || findg( p[gi] ) ){ 
                    p[gi]=bi;
                    return true;
                }
            }
        }
        return false;    
    }
    
    int main(){ 
        int n;
        while(scanf("%d",&n)!=EOF){ 
            bc = 0;
            gc = 0;
            fill(p,p+100,-1);
            for(int i=0;i<n;i++){ 
                int a=0;
                scanf("%d",&a);
                if(a%2==0){ 
                    b[bc++] = a;
                }else{ 
                    g[gc++] = a;
                }
            }
            
            for(int i=0;i<bc;i++){ 
                for(int j=0;j<gc;j++){ 
                    l[i][j] = isp(b[i]+g[j]);
                }
            }
            
            int cnt=0;
            for(int i=0;i<bc;i++){ 
                fill(v,v+100,0);
                if(findg(i)){ 
                    cnt++;
                }
            }
            cout<<cnt<<endl;
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

[Link 1]: https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e?tpId=37&tqId=21251&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking&tab=answerKey
[Link 2]: https://baike.baidu.com/item/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95/9089246?fr=aladdin
[Link 3]: https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E5%9B%BE/9089095?fr=aladdin
[Link 4]: https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E5%9B%BE%E5%8C%B9%E9%85%8D/9089174?fr=aladdin
[https_zhuanlan.zhihu.com_p_96229700]: https://zhuanlan.zhihu.com/p/96229700
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20221021/4dc3980232cd4ffda0339017f63027df.png