记录编号	249774	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 数字配对	最终得分	100
用户昵称	铁策	是否通过	通过
代码语言	C++	运行时间	0.066 s
提交时间	2016-04-13 17:04:45	内存使用	1.36 MiB

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <queue>
#include <cstring>
#define INF 99999999999LL
using namespace std;
inline int readint()
{
	int x = 0, flag = 1;
	char c = getchar();
	if (c == '-')
	{
		flag = -1;
		c = getchar();
	}
	else
		while (!isdigit(c))
		{
			c = getchar();
			if (c == '-')
			{
				flag = -1;
				c = getchar();
				break;
			}
		}
	x = c - '0';
	c = getchar();
	while (isdigit(c))
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * flag;
}
int n;
int a[200], b[200], c[200];
bool link[200][200];
int color[200];
inline bool checkprime(int x)
{
	if (x == 1)
		return false;
	for (int i = 2; i * i <= x; i++)
		if (x % i == 0)
			return false;
	return true;
}
void div(int now)
{
	for (int i = 0; i < n; i++)
		if (link[now][i] && color[i] == -1)
		{
			color[i] = color[now] ^ 1;
			div(i);
		}
}
int S, T;
long long cap[210][210], flow[210][210], fee[210][210];
inline void Link(int s, int t, long long a, long long b)
{
	cap[s][t] = a;
	fee[s][t] = b;
	fee[t][s] = -b;
}
long long sumflow, sumfee;
bool vis[210];
int pre[210];
long long dis[210];
bool SPFA()
{
	queue<int> q;
	memset(vis, 0, sizeof(vis));
	memset(pre, -1, sizeof(pre));
	for (int i = 0; i <= T; i++)
		dis[i] = INF;
	vis[S] = true, dis[S] = 0;
	q.push(S);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = false;
		for (int i = 0; i <= T; i++)
		{
			if (cap[u][i] - flow[u][i] && dis[i] > dis[u] + fee[u][i])
			{
				dis[i] = dis[u] + fee[u][i];
				pre[i] = u;
				if (!vis[i])
				{
					q.push(i);
					vis[i] = true;
				}
			}
		}
	}
	return (dis[T] < INF);
}
void getflow()
{
	long long lsflow;
	while (SPFA())
	{
		lsflow = INF + 1;
		int j = T;
		for (int i = pre[T]; i != -1; i = pre[i])
		{
			if (cap[i][j] - flow[i][j] < lsflow)
				lsflow = cap[i][j] - flow[i][j];
			j = i;
		}		
		j = T;
		for (int i = pre[T]; i != -1; i = pre[i])
		{
			flow[i][j] += lsflow;
			flow[j][i] -= lsflow;
			j = i;
		}
		if (sumfee + dis[T] * lsflow > 0)
		{
			int ls = -sumfee / dis[T];
			sumflow += ls;
			return;
		}
		sumflow += lsflow;
		sumfee += dis[T] * lsflow;
	}
	return;
}
int main()
{
	freopen("menci_pair.in", "r", stdin);
	freopen("menci_pair.out", "w", stdout);
	n = readint();
	for (int i = 0; i < n; i++)
		a[i] = readint();
	for (int i = 0; i < n; i++)
		b[i] = readint();
	for (int i = 0; i < n; i++)
		c[i] = readint();
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (a[i] % a[j] == 0 && checkprime(a[i] / a[j]))
				link[i][j] = link[j][i] = true;
	for (int i = 0; i < n; i++)	
		color[i] = -1;
	for (int i = 0; i < n; i++)	
		if (color[i] == -1)
		{
			color[i] = (i % 2);
			div(i);
		}
	S = n, T = n + 1;
	for (int i = 0; i < n; i++)
	{
		if (!color[i])
			Link(S, i, b[i], 0);
		else
			Link(i, T, b[i], 0);
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (color[i] == 0 && color[j] == 1)
				if (link[i][j])
					Link(i, j, min(b[i], b[j]), (long long)c[i] * c[j] * (-1));
	getflow();
	printf("%lld\n", sumflow);
	return 0;
}