Prime Set
Time Limit: 2 Seconds Memory Limit: 131072 KB
Given an array of integers , we say a set is a prime set of the given array, if and is prime.
BaoBao has just found an array of integers in his pocket. He would like to select at most prime set of that array to maximize the size of the union of the selected sets. That is to say, to maximize by carefully selecting and , where and is a prime set of the given array. Please help BaoBao calculate the maximum size of the union set.
Input
There are multiple test cases. The first line of the input is an integer , indicating the number of test cases. For each test case:
The first line contains two integers and (, ), their meanings are described above.
The second line contains integers (), indicating the given array.
It's guaranteed that the sum of over all test cases will not exceed .
Output
For each test case output one line containing one integer, indicating the maximum size of the union of at most prime set of the given array.
Sample Input
4 4 2 2 3 4 5 5 3 3 4 12 3 6 6 3 1 3 6 8 1 1 1 0 1Sample Output
4 3 6 0Hint
For the first sample test case, there are 3 prime sets: {1, 2}, {1, 4} and {2, 3}. As , we can select {1, 4} and {2, 3} to get the largest union set {1, 2, 3, 4} with a size of 4.
For the second sample test case, there are only 2 prime sets: {1, 2} and {2, 4}. As , we can select both of them to get the largest union set {1, 2, 4} with a size of 3.
For the third sample test case, there are 7 prime sets: {1, 3}, {1, 5}, {1, 6}, {2, 4}, {3, 5}, {3, 6} and {5, 6}. As , we can select {1, 3}, {2, 4} and {5, 6} to get the largest union set {1, 2, 3, 4, 5, 6} with a size of 6.
题意：给你n个数你需要选出k对数，使得覆盖尽可能多的数。
思路：还是比较容易想到二分图最大匹配的。
对于可以构成素数的数下标进行建边，跑匈牙利算法。
注意：已经选过的点不能再选。所以在匹配时需要加条件。当前点未匹配则可以进行匹配。（就是这个地方，题解都没说，害的我一度以为自己的匈牙利算法模板是假的，题解大神们能不能长点心，这样对萌新很不友好的。）
所以这个题并不是匈牙利算法的模板题，而是要进行修改。
获得最大匹配数sum以后，若k<=sum，则答案明显就是2*k，否则就是
2*sum+min(k-sum,图中建了边的而且未匹配的点的个数)
所以建了边的点我们要标记。
代码:
#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f3f3f3f3fLL #define maxn 3010 #define maxm 2000010 using namespace std; int n,m,k,p,ans,sum; int g[maxn],us[maxn],a[maxn]; bool ok[maxm]; vector<int>vc[maxn]; bool dfs(int u) { us[u]=true; for(int v=0;v<vc[u].size();v++) { if(!us[vc[u][v]]){ us[vc[u][v]]=true; if(g[vc[u][v]]==-1||dfs(g[vc[u][v]])){ g[vc[u][v]]=u; g[u]=vc[u][v]; return true; } } } return false; } int pipei() { int ans=0; for(int u=1;u<=n;u++) { if(g[u]==-1) { memset(us,0,sizeof(us)); if(dfs(u)) ans++; } } return ans; } int main() { ok[1]=1; for(int i=2;i<maxm;++i){ for(ll j=(ll)i*(ll)i;j<maxm;j+=(ll)i){ ok[j]=1; } } int T,cas=1,x,y,c; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { vc[i].clear(); g[i]=0; scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) if(!ok[a[i]+a[j]]) { vc[i].push_back(j); vc[j].push_back(i); g[i]=g[j]=-1; } } int sum=pipei(); if(sum>=k) printf("%d\n",2*k); else { int cnt=0; for(int i=1;i<=n;i++) if(g[i]==-1) cnt++; int ans=sum*2+min(k-sum,cnt); printf("%d\n",ans); } } return 0; } /* 4 4 2 2 3 4 5 5 3 3 4 12 3 6 6 3 1 3 6 8 1 1 1 0 1 */
