题目描述
题解：
这个题真的是巨坑，经过了6个WA，2个TLE，1个RE后才终于搞出来，中间都有点放弃希望了。。。
主要是一定要注意longlong！
下面开始说明题解。
朴素的想法是：
如果两个数字可以匹配，那么连一条边，那么问题就转化成了一个图的最大边匹配。
然而，一般图的最大边匹配是NP的，所以竞赛中一定不会出。
所以，这种题目一般会满足二分图性质。
我们可以跑几组大数据，进行二分图染色，发现的确是二分图。
仔细思考就可以发现，如果我们设f[i]为i的质因数个数，那么如果i和j可以配对，他们的f值奇偶性一定不同！
所以这个图一定是二分图。
跑一遍最小（最大）费用流就好辣。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e6;
const ll inf = 1e15;
int prime[maxn + 10], check[maxn + 10];
int s, t;
int n, cnt;
void init() {
memset(check, 0, sizeof(check));
cnt = 0;
for (int i = 2; i <= maxn; i++) {
if (!check[i])
prime[cnt++] = i;
for (int j = 0; j < cnt; j++) {
if (i * prime[j] > maxn)
break;
check[i * prime[j]] = true;
if (i % prime[j] == 0)
break;
}
}
}
const int N = 300;
ll a[N], b[N], c[N];
struct edge {
int from, to;
ll cap, flow, cost;
};
vector<ll> G[N];
vector<edge> E;
void add_edge(int from, int to, ll cap, ll cost) {
E.push_back((edge){from, to, cap, 0, cost});
E.push_back((edge){to, from, 0, 0, -cost});
int m = E.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
int calc(int x) {
int ret = 0;
for (int i = 0; prime[i] <= x; i++) {
if (x % prime[i] == 0) {
while (x % prime[i] == 0 && x) {
ret++;
x /= prime[i];
}
}
}
return ret;
}
int pre[N];
int inq[N];
ll dist[N];
ll fi[N];
bool spfa(ll &flow, ll &cost) {
for (int i = 0; i <= n + 1; i++) {
dist[i] = -inf;
}
memset(inq, 0, sizeof(inq));
dist[s] = 0, inq[s] = 1, pre[s] = 0, fi[s] = inf;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = 0;
for (int i = 0; i < G[u].size(); i++) {
edge &e = E[G[u][i]];
if (e.cap > e.flow && dist[e.to] < dist[u] + e.cost) {
dist[e.to] = dist[u] + e.cost;
pre[e.to] = G[u][i];
fi[e.to] = min(fi[u], e.cap - e.flow);
if (!inq[e.to]) {
q.push(e.to);
inq[e.to] = 1;
}
}
}
}
if (dist[t] <= -inf)
return false;
if (cost + dist[t] * fi[t] < 0) {
ll temp = cost / (-dist[t]); //temp:还能够增加的流
flow += temp;
return false;
}
flow += fi[t];
cost += dist[t] * fi[t];
int u = t;
while (u != s) {
E[pre[u]].flow += fi[t];
E[pre[u] ^ 1].flow -= fi[t];
u = E[pre[u]].from;
}
return true;
}
ll mcmf(int s, int t) {
ll flow = 0;
ll cost = 0;
while (spfa(flow, cost))
;
return flow;
}
int main() {
init();
// freopen("input", "r", stdin);
scanf("%d", &n);
s = 0, t = n + 1;
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%lld", &b[i]);
for (int i = 1; i <= n; i++)
scanf("%lld", &c[i]);
for (int i = 1; i <= n; i++) {
int f1 = calc(a[i]), f2;
for (int j = 1; j <= n; j++) {
f2 = calc(a[j]);
if ((f1 % 2 == 1) && ((f2 == f1 - 1 && a[i] % a[j] == 0) ||
(f1 == f2 - 1 && a[j] % a[i] == 0))) {
add_edge(i, j, inf, c[i] * c[j]);
}
}
if (f1 % 2 == 1)
add_edge(s, i, b[i], 0);
else
add_edge(i, t, b[i], 0);
}
ll ans = mcmf(s, t);
printf("%lld
", ans);
}