题解 | #素数伴侣#

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

const int th3 = 60000;
const int maxn = 110;
int find_min(int *a,int len)
{
    int Min = 999999,position = 0;
    for(int i = 1;i <= len; ++i)
    if(a[i] < Min && a[i])
    {
        Min = a[i];
        position = i;
    }
    return position;
}
int find_friend(bool *a,int len)
{
    for(int i = 1;i <= len; ++i)
    if(a[i])return i;
    return 0;
}
int main()
{
    bool notSu[th3+1] = {0};
    int args[maxn];
    int inDegree[maxn] = {0};
    bool primFriend[maxn][maxn] = {0};
    int n;

    scanf("%d",&n);
    for(int i = 1;i <= n; ++i)
    scanf("%d",&args[i]);

    vector<int>prim;
    notSu[1] = 1;
    for(int i=2;i <= th3; ++i)
    {
        if(!notSu[i])prim.push_back(i);

        for(auto j = prim.begin(); j != prim.end() && i*(*j) <= th3; ++j)
            notSu[i*(*j)] = 1;

    }
    for(int i = 1;i < n; ++i)
    for(int j = i+1;j <= n; ++j)
    if(!notSu[ args[i] + args[j] ])
    {
        primFriend[i][j] = 1;
        primFriend[j][i] = 1;
        ++inDegree[i];
        ++inDegree[j];
    }

    int cnt = 0,pos;
    while(pos = find_min(inDegree, n))
    {
        int friendPos = find_friend(primFriend[pos],n);
        
        for(int i = 1;i <= n; ++i)
        if(primFriend[pos][i])
        {
            primFriend[pos][i] = 0;
            primFriend[i][pos] = 0;
            --inDegree[i];
        }

        
        for(int i = 1;i <= n; ++i)
        if(primFriend[friendPos][i])
        {
            primFriend[friendPos][i] = 0;
            primFriend[i][friendPos] = 0;
            --inDegree[i];
        }
        inDegree[pos] = 0;
        inDegree[friendPos] = 0;
        ++cnt;
    }
    printf("%d\n",cnt);

    return 0;
}

先欧拉筛60000之内的素数，存到表里。

然后对任何两个可以成为素数伴侣的数（每个数都是一个点）连边，并记录每个点的度数。然后开始给节点相亲，每次找到度数最小的点，并让它随便找一个连了边的邻接点，相亲成功。把它俩从图里删除，并销毁跟它们有关的所有边，当然，记得更新度数。直到没法再相亲为止。