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

本文主要是介绍[华为机试]素数伴侣 【匈牙利算法：最大二分匹配】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接

百度百科

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

判断方法，染色法

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

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

匈牙利算法

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

知乎一篇写的很不错的文章
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;
}

这篇关于[华为机试]素数伴侣 【匈牙利算法：最大二分匹配】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！