记录编号	249460	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 数字配对	最终得分	100
用户昵称	Fancy	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2016-04-12 19:41:34	内存使用	1.13 MiB

#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=1e5+1;
const long long inf=1e16;
int n,S,T,L,R,mid,Flow;
int totp,notp[maxn],prime[maxn];
int col[210],head1[210],next1[2000],to1[2000];
int ecnt,used[210],head[210],pre[210],to[2000],rest[2000],next[2000];
long long Cost,ds[210],cost[2000];
queue<int> Q;
struct node { int a,b,c; } a[210];
inline bool cmp(const node &x,const node &y) { return x.a<y.a; }
inline void PRE()
{
	notp[1]=1;
	for(int i=2;i<maxn;i++)
	{
		if(!notp[i]) prime[++totp]=i;
		for(int j=1,p=2;j<=totp&&p*i<maxn;p=prime[++j])
		{
			notp[p*i]=1;
			if(!(i%p)) break;
		}
	}
}
inline bool isPrime(int x)
{
	if(x<maxn) return !notp[x];
	for(int i=1,p=2;i<=totp&&p*p<=x;p=prime[++i])
	  if(!(x%p)) return 0;
	return 1;
}
inline void Dfs(int x)
{
	for(int e=head1[x],y=to1[e];e;e=next1[e],y=to1[e])
	  if(!col[y]) col[y]=col[x]^1,Dfs(y);
}
inline void Addedge(int x,int y,int r,long long c)
{
	to[++ecnt]=y;rest[ecnt]=r;cost[ecnt]=c;next[ecnt]=head[x];head[x]=ecnt;
	to[++ecnt]=x;rest[ecnt]=0;cost[ecnt]=-c;next[ecnt]=head[y];head[y]=ecnt;
}
inline bool Spfa()
{
	for(int i=0;i<=T;i++) ds[i]=inf,used[i]=0;
	Q.push(S);ds[S]=0;used[S]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();used[x]=0;
		for(int e=head[x],y=to[e];e;e=next[e],y=to[e])
		  if(rest[e]&&ds[x]+cost[e]<ds[y])
		  {
		  	ds[y]=ds[x]+cost[e];
		  	pre[y]=e;
		  	if(!used[y]) Q.push(y),used[y]=1; 
		  }
	}
	return ds[T]<inf;
}
inline pair<int,long long> Update()
{
	int flow=0x7fffffff;
	for(int e=pre[T];e;e=pre[to[e^1]])
	  if(rest[e]<flow) flow=rest[e];
	for(int e=pre[T];e;e=pre[to[e^1]])
	  rest[e]-=flow,rest[e^1]+=flow;
	return make_pair(flow,(long long)flow*ds[T]);
}
int main()
{
	freopen("menci_pair.in","r",stdin);
	freopen("menci_pair.out","w",stdout);
	scanf("%d",&n);PRE();T=n+1;
	for(int i=1;i<=n;i++) scanf("%d",&a[i].a);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].b);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].c);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<i;j++)
	    if(!(a[i].a%a[j].a)&&isPrime(a[i].a/a[j].a))
	    {
	    	to1[++ecnt]=j,next1[ecnt]=head1[i],head1[i]=ecnt;
	    	to1[++ecnt]=i,next1[ecnt]=head1[j],head1[j]=ecnt;
	    }
	for(int i=1;i<=n;i++) if(!col[i]) col[i]=2,Dfs(i);
	ecnt=1;
	for(int i=1;i<=n;i++)
	{
		if(col[i]&1)
		{
			Addedge(S,i,a[i].b,0);
			for(int e=head1[i],j=to1[e];e;e=next1[e],j=to1[e])
	  		  Addedge(i,j,0x3fffffff,-(long long)a[i].c*a[j].c);
		}
		else Addedge(i,T,a[i].b,0);
	}
	while(Spfa())
	{
		pair<int,long long> aa=Update();
		if(Cost-aa.second<0) {printf("%d\n",Flow+Cost/ds[T]);return 0;	}
		else Flow+=aa.first,Cost-=aa.second;
	} 
	printf("%d\n",Flow);
}