HJ28 素数伴侣

题目描述

​ 若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。

​ 现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。

示例

输入：

4
2 5 6 13

输出：

2

思路

素数伴侣是指两个和为素数的数字，数字可以分为奇数、偶数，奇+偶=奇（可能是素数），而其他组合都是偶数，有质因子2，都是质数。那么问题转化为：给出N个奇数、M个偶数，若某个奇数跟某个偶数和为素数，则两个数字可以配对，求最多能有多少配对。

即：无权二分图最大匹配

Code

#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int link[105];///link[i] = v; 选项i 分配给任务v
bool vis[105];///在为任务v配对时 选项i是否被访问过

vector<int> odd;
vector<int> even;
vector<int> vec[105];

bool dfs(int v) {
    for (int i = 0; i < vec[v].size(); ++i) {
        int to = vec[v][i];
        if (!vis[to]) {
            vis[to] = 1;
            if (link[to] == -1 || dfs(link[to])) {
                link[to] = v;
                return 1;
            }
        }
    }
    return 0;
}

void solve() {
    int ans = 0;
    memset(link, -1, sizeof(link));
    for (int i = 0; i < odd.size(); ++i) {
        memset(vis, 0, sizeof(vis));
        if (dfs(i))
            ans++;
    }
    cout << ans << '\n';
}

bool isPrime(int n) {
    if(n <= 1)
        return false;
    for(int i = 2; i * i <= n; ++i)
        if(n % i == 0)
            return false;
    return true;
}

int main() {
    int n, t;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &t);
        if(t % 2 == 0) even.push_back(t);
        else odd.push_back(t);
    }
    int sz = odd.size();
    int len = even.size();
    for(int i = 0; i < sz; ++i) {
        for(int j = 0; j < len; ++j) {
            if(isPrime(odd[i] + even[j])) {
                vec[i].push_back(j);//用下标代替数字，数字在这之后没意义了
            }
        }
    }

    solve();
    return 0;
}

该算法有几个点：

1. 处理好数据，存到vector<int> vec[105]
2. 算法开始时初始化link数组
3. 为某个元素寻找匹配时初始化vis数组

即vec、link、vis数组是关键与核心，理解了这三个数组的作用就能写出这个算法。