题意:给你n个数,你可以选择2个和为质数的数为一对,每个数可以重复选择,你最多选k对,问你最多能选多少个不同数出来
题解:首先思考怎么样的数和为质数,2个偶数相加不行,除了1+1以外2个奇数相加不行,那么大致上,就是偶数+奇数,
这样很明显的发现这就是一个二分图,而且这是自动分好的,并不需要你建边的时候特殊考虑
所以对于能够加成质数的组合连边,跑最大匹配,如果现在有大于等于k个,那答案肯定就是选k个,每个里面一奇一偶,所以答案==k*2
可要现在不够k个呢?
还是先选ans*2个,剩下的,最好拿个样例画图出来,我们发现那些没在最大匹配的点,还可以有连向匹配里点的边,这时候选一条,答案就只能加1
所以答案就加上这种边的数量,当然也要小于总边数也要小于k,
(这里其实就利用匹配里的"板凳数组",初始化-1,有板凳坐就是0,最后剩下还是0的那些就是可以连一条边的)
那些人的题解好像对1进行特殊处理,搞的很复杂麻烦,可是我们再细想,选1+1这对,前提是1没法和任何数相加为质数了,不然选不到1+1,且收益也只有1
因为1+1只能带来1这个1个数,所以不用考虑,它本身就不会被纳入最大匹配里,这条边,只有在需要补的时候用上
1 #include<bits/stdc++.h> 2 #define N 3005 3 #define M 2000010 4 using namespace std; 5 int pri[M],n,k,T,ans,sum,a[N],used[N],col[N]; 6 vector<int>g[N]; 7 int dfs(int x) 8 { 9 used[x]=1; 10 for (int i=0;i<g[x].size();i++) 11 { 12 int y=g[x][i]; 13 if (!used[y]) 14 { 15 used[y]=1; 16 if (col[y]==0 || dfs(col[y])) 17 { 18 col[y]=x; 19 col[x]=y; 20 return 1; 21 } 22 } 23 } 24 return 0; 25 } 26 int main() 27 { 28 for (int i=2;i<M;i++) 29 if (!pri[i]) 30 for (int j=i*2;j<M;j+=i) pri[j]=1; 31 scanf("%d",&T); 32 while (T--) 33 { 34 scanf("%d%d",&n,&k); 35 memset(col,-1,sizeof(col)); 36 for (int i=1;i<=n;i++) g[i].clear(); 37 ans=sum=0; 38 for (int i=1;i<=n;i++) scanf("%d",&a[i]); 39 for (int i=1;i<=n;i++) 40 for (int j=i+1;j<=n;j++) 41 if (!pri[a[i]+a[j]]) 42 { 43 col[i]=0; 44 col[j]=0; 45 g[i].push_back(j); 46 g[j].push_back(i); 47 } 48 for (int i=1;i<n;i++) 49 if (!col[i]) 50 { 51 memset(used,0,sizeof(used)); 52 ans+=dfs(i); 53 } 54 if (ans>=k) printf("%d ",k*2);else 55 { 56 for (int i=1;i<=n;i++) if (!col[i]) sum++; 57 printf("%d ",ans*2+min(k-ans,sum)); 58 } 59 } 60 }