记录编号	249340	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 数字配对	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.126 s
提交时间	2016-04-12 16:14:26	内存使用	12.70 MiB

#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int maxp=32000;
const int maxn=500;
const LL inf=1e15;
int n,m,p[maxn],cnt=0,h[maxn],tot=1,vis[maxn];
struct edges{int to,next,c;LL w;}G[maxn*maxn*2];
int pre[maxn],a[maxn],b[maxn],c[maxn],S,T,in[maxn],out[maxn];
LL dis[maxn];

void add(int x,int y,int c,LL w){
	G[++tot].to=y;G[tot].next=h[x];h[x]=tot;G[tot].c=c;G[tot].w=w;
	G[++tot].to=x;G[tot].next=h[y];h[y]=tot;G[tot].c=0;G[tot].w=-w;
}

bool spfa(){
	for (int i=S;i<=T;++i)
		{vis[i]=0;pre[i]=-1;dis[i]=-inf;}
	queue<int>q; q.push(S); vis[S]=1; dis[S]=0;
	while (!q.empty()){
		int u=q.front(); q.pop(); vis[u]=0;
		for (int i=h[u];i;i=G[i].next){
			int v=G[i].to;
			if (dis[v]<dis[u]+G[i].w&&G[i].c>0){
				pre[v]=i; dis[v]=dis[u]+G[i].w;
				if (!vis[v]){vis[v]=1;q.push(v);}
			}
		}
	}return pre[T]!=-1;
}

void max_cost_flow(){
	int retflow=0; LL cost=0;
	while (spfa()){
		int flow=0x7fffffff;
		for (int i=pre[T];i!=-1;i=pre[G[i^1].to])
		    flow=min(flow,G[i].c);
		LL tmp=cost;
		cost+=1LL*flow*dis[T];
		if (cost<0){
			retflow+=tmp/(-dis[T]);
			printf("%d",retflow>>1);
			return;
		}
		retflow+=flow;
		for (int i=pre[T];i!=-1;i=pre[G[i^1].to])
		    G[i].c-=flow,G[i^1].c+=flow;
	}printf("%d",retflow>>1);
}

void get_primes(){
	for (int i=2;i<=maxp;++i){
		if (!vis[i]) p[++cnt]=i;
		for (int j=1;j<=cnt&&p[j]*i<=maxp;++j){
			vis[i*p[j]]=1;
			if (i%p[j]==0) break;
		}
	}
}

bool check(int x){
	if (x==1) return 0;
	for (int i=1;i<=cnt;++i){
		if (p[i]*p[i]>x) return 1;
		if (x%p[i]==0) return 0;
	}return 1;
}

int main(){
	freopen("menci_pair.in","r",stdin);
	freopen("menci_pair.out","w",stdout);
	scanf("%d",&n);
	get_primes(); S=0; T=n*2+1;
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	for (int i=1;i<=n;++i) scanf("%d",&b[i]);
	for (int i=1;i<=n;++i) scanf("%d",&c[i]);
	for (int i=1;i<=n;++i)
	    in[i]=i,out[i]=n+i,add(S,in[i],b[i],0),add(out[i],T,b[i],0);
	for (int i=1;i<=n;++i)
	    for (int j=1;j<=n;++j)
	        if (a[i]%a[j]==0&&check(a[i]/a[j]))
	            add(in[j],out[i],0x7fffffff,1LL*c[i]*c[j]),
	            add(in[i],out[j],0x7fffffff,1LL*c[i]*c[j]);
	max_cost_flow();
}