zoj3988 二分图匹配

给一个数组，对于每两个数加起来为素数那么就是一个集合，求不超过k个集合的最多数是多少

解法：二分图匹配，先打素数筛，预处理边集，匹配完之后分两种情况k>匹配数，那么可以直接输出匹配数*2，否则可以选取匹配数*2+min（k-匹配数，剩余没有匹配的而且有边的点），这里是因为没有匹配的点有边，连着之前匹配过的点，我们可以复用，只要保证不超过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|1

using 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
",2*k);
        else printf("%d
",sum1*2+min(k-sum1,sum2));
    }
    return 0;
}
/************

************/