AtCoder Beginner Contest 263 G.Erasing Prime Pairs(二分图最大匹配-网络流)_atcode 二分图匹配

题目

黑板上有n(n<=100)个不同的数，第i个数ai(1<=ai<=1e7)出现了bi(1<=1e9)次，

你每次可以选择当前黑板上存在的两个数x、y，满足x+y是质数，擦掉这两个数，

求可以擦掉的最大次数

思路来源

AtCoder Beginner Contest 题目选解 - 云浅知处 - 博客园

题解

先考虑a,b,c互不相同的情形，三个素数里面必有至少两个数是奇素数，

不妨a+b和a+c是奇数，则b和c同奇偶，b+c之和必为偶数，b不等于c则b+c不等于2，

所以b+c不为素数，原图是一个近似二分图的图，

但是，注意到b=c=1的时候，例如a=4,b=c=1，两两匹配也均为素数

自己wa的过程和思路来源基本一模一样，所以直接粘过来了…

考虑原图除了1以外，其余部分都是二分图，1和1自己能构成素数2，有一个自环

所以考虑把1拆成2个点，入点和出点，再连边，答案就对了

无向图最大匹配拆入点和出点，答案需要除以2这个也是典中典了…

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=210,N=maxn;
const int maxm=maxn*maxn*5+10,M=2e7+10;
int level[maxn];
int head[maxn],cnt;
int t,n,m,a[N],b[N],col[N],to[N];
int ss,ee;
bool ok[M];
int prime[M],tot;
struct edge{int v,nex;ll w;}e[maxm];
void init()
{
	cnt=0;
	memset(head,-1,sizeof head);
}
void add(int u,int v,ll w)
{
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt++;
}
void add2(int u,int v,ll w,bool op)//是否为有向图 
{
	add(u,v,w);
	add(v,u,op?0:w);
}
bool bfs(int s,int t)
{
	queue<int>q;
	memset(level,0,sizeof level);
	level[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		if(x==t)return 1;
		for(int u=head[x];~u;u=e[u].nex)
		{
			int v=e[u].v;ll w=e[u].w;
			if(!level[v]&&w)
			{
				level[v]=level[x]+1;
				q.push(v);
			}
		}
	}
	return 0;
}
ll dfs(int u,ll maxf,int t)
{
	if(u==t)return maxf;
	ll ret=0;
	for(int i=head[u];~i;i=e[i].nex)
	{
		int v=e[i].v;ll w=e[i].w;
		if(level[u]+1==level[v]&&w)
		{
			ll MIN=min(maxf-ret,w);
			w=dfs(v,MIN,t);
			e[i].w-=w;
			e[i^1].w+=w;
			ret+=w;
			if(ret==maxf)break;
		}
	}
	if(!ret)level[u]=-1;//优化,防止重搜,说明u这一路不可能有流量了 
	return ret;
}
ll Dinic(int s,int t)
{
	ll ans=0;
	while(bfs(s,t))
	ans+=dfs(s,INF,t);
	return ans;
}
void sieve()
{
	for(ll i=2;i<M;++i)
	{
		if(!ok[i])prime[tot++]=i;
		for(int j=0;j<tot;++j)
		{
			if(i*prime[j]>=M)break;
			ok[i*prime[j]]=1;
			if(i%prime[j]==0)break; 
		}
	}
}
int main(){
	init();
	sieve();
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&a[i],&b[i]);
	}
	ss=2*n+1;ee=2*n+2;
	for(int i=1;i<=n;++i){
		add2(ss,i,b[i],1);
		add2(i+n,ee,b[i],1);
		for(int j=1;j<=n;++j){
			if(!ok[a[i]+a[j]]){
				add2(i,j+n,min(b[i],b[j]),1);
				add2(j,i+n,min(b[i],b[j]),1);
			}
		}
	}
	ll ans=Dinic(ss,ee);
	printf("%lld\n",ans/2);
	return 0;
}
//1 6 7 12