【JSOI2016】反质数序列（二分图，最小割）

这都能扯到二分图上，看来是我做题太少了。

不是质数的情况有很多种，不妨考虑一下包含质数的情况。

考虑到质数只有可能是奇数+偶数构成的（\(2\) 除外，不过 \(2\) 只能由 \(1+1\) 凑成，所以我们考虑时只考虑一个 \(1\)，其余的 \(1\) 全部不选），所以不妨将所有的数按奇偶分类，构成一个二分图。

然后如果两个数加起来是一个质数，我们就将它们连边。

现在的要求是删除一些点以及与它们相连的边，使得图上不剩下边，这个用最小割解决就行了。

听说这个叫二分图最大独立集（

#include<bits/stdc++.h>

#define N 3010
#define W 100010
#define INF 0x7fffffff

using namespace std;

int n,sum,s,t,a[N];
int tot,prime[W<<1];
int cnt=1,head[N],cur[N],to[N*4+N*N/2],c[N*4+N*N/2],nxt[N*4+N*N/2];
int num[N];
bool notprime[W<<1];

queue<int>q;

void init()
{
	for(int i=2;i<=2e5;i++)
	{
		if(!notprime[i]) prime[++tot]=i;
		for(int j=1;j<=tot&&i*prime[j]<=2e5;j++)
		{
			notprime[i*prime[j]]=1;
			if(!(i%prime[j])) break;
		}
	}
}

void adde(int u,int v,int ci)
{
	to[++cnt]=v;
	c[cnt]=ci;
	nxt[cnt]=head[u];
	head[u]=cnt;
	
	to[++cnt]=u;
	c[cnt]=0;
	nxt[cnt]=head[v];
	head[v]=cnt;
}

bool bfs()
{
	memcpy(cur,head,sizeof(cur));
	memset(num,-1,sizeof(num));
	q.push(s);
	num[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(c[i]&&num[v]==-1)
			{
				num[v]=num[u]+1;
				q.push(v);
			}
		}
	}
	return num[t]!=-1;
}

int dfs(int u,int minflow)
{
	if(u==t||!minflow) return minflow;
	int preflow=0,nowflow;
	for(int i=cur[u];i;i=nxt[i])
	{
		cur[u]=i;
		int v=to[i];
		if(num[v]==num[u]+1&&(nowflow=dfs(v,min(c[i],minflow-preflow))))
		{
			preflow+=nowflow;
			c[i]-=nowflow;
			c[i^1]+=nowflow;
			if(!(minflow-preflow)) break;
		}
	}
	return preflow;
}

int dinic()
{
	int maxflow=0;
	while(bfs())
		maxflow+=dfs(s,INF);
	return maxflow;
}

int main()
{
	init();
	scanf("%d",&n);
	s=1,t=1+n+1;
	bool one=false;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]==1)
		{
			if(!one) one=1;
			else a[i]=0;
		}
		if(a[i])
		{
			sum++;
			if(a[i]&1) adde(s,1+i,1);
			else adde(1+i,t,1);
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i!=j&&a[i]&&a[j]&&(a[i]&1)&&(!(a[j]&1))&&(!notprime[a[i]+a[j]]))
				adde(1+i,1+j,INF);
	printf("%d\n",sum-dinic());
	return 0;
}
/*
8
1 1 2 2 3 4 10 1
*/

原文地址：http://www.cnblogs.com/ez-lcw/p/16837454.html