题解 | #素数伴侣#

一定要注意：左侧零号位置是右侧初始被映射位置，循环标号一定要从1开始加

此外，用Hall Wedding THM的一条引理：二部图有m-a匹配的充要条件是集合A任选k个至少有集合B上k-a个双射，用此方法，可直接循环出答案

#include <stdio.h>
#include <string.h>
#include <math.h>

int numo,nume,numa;
int even[100],odd[100];//二部图点的个数
int edge[100][100];//是否存在边

int isprime(int x)
{
    for(int i=2;i<=sqrt(x)+1;i++)
    {
        if(x%i==0)
        return 0;
    }
    return 1;
}

void hasedge()
{
    int t;
    for(int i=1;i<=numo;i++)
    for(int j=1;j<=nume;j++)
    {
        t=odd[i]+even[j];
        t=isprime(t);
        if(t==1)
        edge[i][j]=1;
        else edge[i][j]=0;    
    }
    return;
}

void divide(int num[])
{
    int i;
    for(i=0,nume=0,numo=0;i<numa;i++)
    {
        if(num[i]%2==0)
        {
            nume+=1;
            even[nume]=num[i];
            
        }
        else{
            numo+=1;
            odd[numo]=num[i];
            
        }
    }
    hasedge();
    return;
}

int wedding(int i)//对i元素开始婚约定理
{
int j;
for(j=1;j<=nume;j++)//偶数集合作为新娘
{
    if(even[j]==0&&edge[i][j]==1)
    {
        even[j]=1;
        if(odd[j]==0||wedding(odd[j])==1)
        {
            odd[j]=i;
            return 1;
        }
    }
 
}
   return 0;
}
int main() {
    int p,sum,num[100];
    sum=0;
    memset(odd,0,sizeof(odd));
    memset(even,0,sizeof(even));
    memset(edge,0,sizeof(edge)); 
    scanf("%d",&numa);
    for(int k=0;k<numa;k++)
    {
        scanf("%d",&num[k]);
    }
    divide(num);
    memset(odd,0,sizeof(odd));
    memset(even,0,sizeof(even));
    for(p=1;p<=numo;++p)
    {
        memset(even,0,sizeof(even));
    if(wedding(p))sum++;
    }
    printf("%d",sum);
        return 0;
    }