欧派网站谁做的/新东方

题目

黑板上有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