记录编号	363010	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 数字配对	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2017-01-09 20:22:00	内存使用	2.08 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=215,maxe=maxn*maxn;
struct edge{int to,cap,prev;long long cost;}e[maxe<<1];
int F(int);
void addedge(int,int,int,long long);
void AddEdge(int,int,int,long long);
int maxcostflow();
void SPFA();
vector<int>G[maxn];
int last[maxn],len=0,p[maxn];
long long dis[maxn];
bool inq[maxn];
int n,s,t,a[maxn],b[maxn],c[maxn],f[maxn];
int main(){
	freopen("menci_pair.in","r",stdin);
	freopen("menci_pair.out","w",stdout);
	memset(last,-1,sizeof(last));
	scanf("%d",&n);
	s=n+1;t=s+1;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		f[i]=F(a[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
		if(f[i]&1)addedge(s,i,b[i],0);
		else addedge(i,t,b[i],0);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&c[i]);
		for(int j=1;j<i;j++){
			if(f[i]==f[j]+1){
				if(a[i]%a[j]==0){
					if(f[i]&1)addedge(i,j,(~0u)>>1,(long long)c[i]*c[j]);
					else addedge(j,i,(~0u)>>1,(long long)c[i]*c[j]);
				}
			}
			else if(f[j]==f[i]+1){
				if(a[j]%a[i]==0){
					if(f[i]&1)addedge(i,j,(~0u)>>1,(long long)c[i]*c[j]);
					else addedge(j,i,(~0u)>>1,(long long)c[i]*c[j]);
				}
			}
		}
	}
	printf("%d",maxcostflow());
	return 0;
}
int F(int n){
	int m=(int)(sqrt(n)+0.5),ans=0;
	for(int i=2;i<=m;i++)if(n%i==0)do{
		n/=i;
		ans++;
	}while(n%i==0);
	if(n>1)ans++;
	return ans;
}
void addedge(int x,int y,int z,long long w){
	AddEdge(x,y,z,w);
	AddEdge(y,x,0,-w);
}
void AddEdge(int x,int y,int z,long long w){
	e[len].to=y;
	e[len].cap=z;
	e[len].cost=w;
	e[len].prev=last[x];
	last[x]=len++;
}
int maxcostflow(){
	int flow=0,delta,x;
	long long cost=0;
	while(SPFA(),dis[t]>-0x4000000000000000ll){
		if(dis[t]>=0)delta=(~0u)>>1;
		else if(!(delta=cost/-dis[t]))break;
		for(x=t;x!=s;x=e[p[x]^1].to)delta=min(delta,e[p[x]].cap);
		flow+=delta;
		cost+=dis[t]*delta;
		for(x=t;x!=s;x=e[p[x]^1].to){
			e[p[x]].cap-=delta;
			e[p[x]^1].cap+=delta;
		}
	}
	return flow;
}
void SPFA(){
	int x;
	fill(dis+1,dis+t+1,-0x4000000000000000ll);
	queue<int>q;
	q.push(s);
	dis[s]=0;
	while(!q.empty()){
		x=q.front();
		q.pop();
		inq[x]=false;
		for(int i=last[x];i!=-1;i=e[i].prev)if(e[i].cap>0&&dis[e[i].to]<dis[x]+e[i].cost){
			dis[e[i].to]=dis[x]+e[i].cost;
			p[e[i].to]=i;
			if(!inq[e[i].to]){
				inq[e[i].to]=true;
				q.push(e[i].to);
			}
		}
	}
}