【BZOJ4514】[Sdoi2016]数字配对

Description

有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。

若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数，

那么这两个数字可以配对，并获得 ci×cj 的价值。

一个数字只能参与一次配对，可以不参与配对。

在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。

Input

第一行一个整数 n。

第二行 n 个整数 a1、a2、……、an。

第三行 n 个整数 b1、b2、……、bn。

第四行 n 个整数 c1、c2、……、cn。

Output

一行一个数，最多进行多少次配对

Sample Input

3
2 4 8
2 200 7
-1 -2 1

Sample Output

HINT

n≤200，ai≤10^9，bi≤10^5，∣ci∣≤10^5

题解：一看到数据范围和大致题意，直接想到费用流，但是想了一会，发现建图好像并不容易。

为了方便分解质因数，我们现将1-100000中的质数都筛出来，这样我们可以较快速的判断两个数的商是否是质数。但是如何建图呢？这一些数好像很难构成一个二分图。但是如果我们将所有数按照所含的质因子总数奇偶分类，就得到了一个二分图，连边跑个最大费用流即可。

当我们找到一条增广路，使得增广后总权值为负时，直接特判一下最多还能流多少就行了。

#include <cstdio>#include <cstring>#include <iostream>#include <queue>#include <algorithm>using namespace std;typedef long long ll;const ll inf=9223372036854775807;int n,m,cnt,tot,S,T;ll ans,sum;int pri[100010],A[210],B[210],C[210],num[210],to[1000000],next[1000000],inq[210],pe[210],pv[210],head[210];bool np[100010];ll cost[1000000],flow[1000000],dis[210];queue<int> q;int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}bool isp(int x){	if(x<=100000)	return !np[x];	for(int i=1;i<=tot;i++)	if(x%pri[i]==0)	return 0;	return 1;}void add(int a,int b,ll c,ll d){	to[cnt]=b,cost[cnt]=c,flow[cnt]=d,next[cnt]=head[a],head[a]=cnt++;	to[cnt]=a,cost[cnt]=-c,flow[cnt]=0,next[cnt]=head[b],head[b]=cnt++;}int bfs(){	memset(dis,0x80,sizeof(dis));	int i,u;	q.push(S),dis[S]=0;	while(!q.empty())	{		u=q.front(),q.pop(),inq[u]=0;		for(i=head[u];i!=-1;i=next[i])		{			if(dis[to[i]]<dis[u]+cost[i]&&flow[i])			{				dis[to[i]]=dis[u]+cost[i],pe[to[i]]=i,pv[to[i]]=u;				if(!inq[to[i]])	inq[to[i]]=1,q.push(to[i]);			}		}	}	return dis[T]>(ll)0x8080808080808080;}int main(){	n=rd(),S=0,T=n+1;	int i,j,tmp;	memset(head,-1,sizeof(head));	for(i=1;i<=n;i++)	A[i]=rd();	for(i=1;i<=n;i++)	B[i]=rd();	for(i=1;i<=n;i++)	C[i]=rd();	for(np[1]=1,i=2;i<=100000;i++)	{		if(!np[i])	pri[++tot]=i;		for(j=1;j<=tot&&i*pri[j]<=100000;j++)		{			np[i*pri[j]]=1;			if(i%pri[j]==0)	break;		}	}	for(i=1;i<=n;i++)	{		tmp=A[i];		for(j=1;j<=tot&&pri[j]<=tmp;j++)	while(tmp%pri[j]==0)	tmp/=pri[j],num[i]++;		if(tmp!=1)	num[i]++;	}	for(i=1;i<=n;i++)	{		if(num[i]&1)		{			add(S,i,0,B[i]);			for(j=1;j<=n;j++)	if(abs(num[i]-num[j])==1)				if((A[i]%A[j]==0&&isp(A[i]/A[j]))||(A[j]%A[i]==0&&isp(A[j]/A[i])))	add(i,j,(ll)C[i]*C[j],inf);		}		else	add(i,T,0,B[i]);	}	while(bfs())	{		ll mf=inf;		for(i=T;i!=S;i=pv[i])	mf=min(mf,flow[pe[i]]);		if(sum+mf*dis[T]<0)		{			ans+=sum/(-dis[T]);			break;		}		sum+=mf*dis[T],ans+=mf;		for(i=T;i!=S;i=pv[i])	flow[pe[i]]-=mf,flow[pe[i]^1]+=mf;	}	printf("%lld",ans);	return 0;}

【BZOJ4514】[Sdoi2016]数字配对费用流

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 【BZOJ4514】[Sdoi2016]数字配对 费用流