HJ28 素数伴侣

题面：https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e?tpId=37&tqId=21251&rp=1&ru=%2Fexam%2Foj%2Fta&qru=%2Fexam%2Foj%2Fta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=&dayCountBigMember=365%E5%A4%A9

我的做法是用线性筛先筛出2倍max(a[i]）内的素数，便于后面判断两数之和是否素数。

然后在两数之和为素数的两个点之间连边。

求最大匹配数，我一开始傻了，没想起来这是二分图匹配，没用匈牙利算法，用了dfs，然后n=32就tle了。

后来想起来这是二分图匹配，就用了匈牙利算法。

思路就是对于当前还没有匹配的点，dfs进行匹配，看能否为它找到匹配对象。dfs过程中，如果连边指向的点还没有匹配，或者它所对应的匹配点可以通过dfs再次找到下一个对象，则可以进行匹配，并且答案数目+1.  注意标记，防止进入环中死循环。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,a[110],cnt[110],pd[110][110],maxa;
 4 int MinSS[60010],Prime[60010],numPrime=0,ans=0;
 5 int match[110];
 6 bool isPrime[60010],BeiXuan[110],book[110];
 7 void XianXingShai(int n){
 8     for(int i=2;i<=n;i++){
 9         if(MinSS[i]==0){
10             MinSS[i]=i;
11             isPrime[i]=1;
12             Prime[++numPrime]=i;
13         }
14         for(int j=1;j<=numPrime;j++){
15             if(Prime[j]>MinSS[i]||Prime[j]*i>n)break;
16             MinSS[Prime[j]*i]=Prime[j];
17         }
18     }
19     return;
20 }
21 void initWork(){
22     for(int i=1;i<=n;i++)
23         for(int j=1;j<=n;j++){
24             if(i!=j&&isPrime[a[i]+a[j]])pd[i][++cnt[i]]=j;
25         }
26     return;
27 }
28 bool Dfs(int u){
29     book[u]=1;
30     for(int i=1;i<=cnt[u];i++){
31         int v=pd[u][i];
32         if(match[v]==0||(book[match[v]]==0&&Dfs(match[v]))){
33             match[v]=u;
34             match[u]=v;
35             return 1;
36         }
37     }
38     return 0;
39 }
40 int main(){
41     cin>>n;
42     for(int i=1;i<=n;i++)scanf("%d",&a[i]),maxa=max(maxa,a[i]);
43     maxa*=2;
44     XianXingShai(maxa);
45     initWork();//预处理出能配对的数
46     ans=0;
47     for(int i=1;i<=n;i++){
48         memset(book,0,sizeof(book));
49         if(match[i]==0&&Dfs(i))ans++;
50     }
51     cout<<ans;
52     return 0;
53 }