給一個數(shù)組，對于每兩個數(shù)加起來為素數(shù)那么就是一個集合，求不超過k個集合的最多數(shù)是多少

解法：二分圖匹配，先打素數(shù)篩，預處理邊集，匹配完之后分兩種情況k>匹配數(shù)，那么可以直接輸出匹配數(shù)*2，否則可以選取匹配數(shù)*2+min（k-匹配數(shù)，剩余沒有匹配的而且有邊的點），這里是因為沒有匹配的點有邊，連著之前匹配過的點，我們可以復用，只要保證不超過k個集合就可以了，

#include<bits/stdc++.h> #include<ext/rope> #define fi first #define se second #define mp make_pair #define pb push_back #define pii pair<int,int> #define C 0.5772156649 #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1using namespace std; using namespace __gnu_cxx;const double g=10.0,eps=1e-7; const int N=3000+10,maxn=2000000+10,inf=0x3f3f3f;bool prime[maxn],used[N]; int a[N]; int color[N]; vector<int>v[N]; void getprime() {for(int i=2;i<maxn;i++){if(!prime[i]){for(int j=2*i;j<maxn;j+=i)prime[j]=1;}} } bool match(int x) {used[x]=1;int sz=v[x].size();for(int i=0;i<sz;i++){int u=v[x][i];if(!used[u]){used[u]=1;if(color[u]==0||match(color[u])){color[u]=x;color[x]=u;return 1;}}}return 0; } int main() {getprime();int t;scanf("%d",&t);while(t--){int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);v[i].clear();color[i]=-1;}for(int i=1;i<=n;i++){for(int j=1+i;j<=n;j++){if(!prime[a[i]+a[j]]){v[i].pb(j);v[j].pb(i);color[i]=color[j]=0;}}}int sum1=0,sum2=0;for(int i=1;i<=n;i++){if(color[i]==0){memset(used,0,sizeof used);if(match(i))sum1++;}}for(int i=1;i<=n;i++)if(color[i]==0)sum2++;// for(int i=1;i<=n;i++)cout<<color[i]<<endl;if(sum1>=k)printf("%d\n",2*k);else printf("%d\n",sum1*2+min(k-sum1,sum2));}return 0; } /************************/ View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/acjiumeng/p/7785542.html

總結(jié)

以上是生活随笔為你收集整理的zoj3988 二分图匹配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。