自动搬运

查看原文

来自洛谷，原作者为

	xyz32768 “各方面相差太远”

搬运于2025-08-24 21:56:08，当前版本为作者最后更新于2018-03-10 11:12:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析题目，发现重点在于条件「一个数字只能参与一次配对」。

考虑求出$cnt_i$，表示$a_i$分解质因数之后，每个质因数的指数之和。

那么$a_i$和$a_j$能配对的条件转化为：

$a_i$是$a_j$的倍数，且$cnt_i=cnt_j+1$。

考虑一个二分图的模型。先按照$cnt$的奇偶性，把数字分为两个集合。

1、源点向所有$cnt$为奇数的点连一条容量为$b_i$，费用为$0$的边。

2、所有$cnt$为偶数的点向汇点连一条容量为$b_i$，费用为$0$的边。

3、对于一对$i,j$，如果$a_i$和$a_j$能配对并且$cnt_i$为奇数，则由$i$向$j$连一条边，容量为$\infty$，费用为$ci\times cj$。

然后跑最大费用最大流。但是写法有一些变化：

由于跑最大费用最大流的过程中，每一次增广求出的最长路一定不会大于上一次增广求出的最长路，所以考虑贪心

每一次跑最长路后，沿着最长路，在价值总和不小于$0$的前提下尽可能增加流量。如果找不到增广路或者继续增广一定会使价值总和小于$0$，则已经传输的总流量就是答案。 代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
typedef long long ll;
const int N = 210, M = 5e5 + 5; const ll INF = 1ll << 61;
int n, a[N], b[N], c[N], cnt[N], ecnt = 1, nxt[M], adj[N], st[M], go[M],
frm[M], S, T, len, que[M];
ll cap[M], cost[M], dis[N], sum, ans; bool vis[N];
void add_edge(int u, int v, ll w, ll x) {
    nxt[++ecnt] = adj[u]; adj[u] = ecnt; st[ecnt] = u;
    go[ecnt] = v; cap[ecnt] = w; cost[ecnt] = x;
    nxt[++ecnt] = adj[v]; adj[v] = ecnt; st[ecnt] = v;
    go[ecnt] = u; cap[ecnt] = 0; cost[ecnt] = -x;
}
int sigma(int n) {
    int i, S = sqrt(n), tot = 0; for (i = 2; i <= S; i++)
        while (n % i == 0) n /= i, tot++; if (n > 1) tot++; return tot;
}
bool spfa() {
    int i; for (i = S; i <= T; i++) vis[i] = 0, dis[i] = -INF;
    dis[que[len = 1] = S] = 0; for (i = 1; i <= len; i++) {
        int u = que[i]; vis[u] = 0;
        for (int e = adj[u], v; e; e = nxt[e])
            if (cap[e] && dis[u] + cost[e] > dis[v = go[e]]) {
                dis[v] = dis[u] + cost[frm[v] = e];
                if (!vis[v]) vis[que[++len] = v] = 1;
            }
    }
    return dis[T] > -INF;
}
bool add() {
    ll fl = INF, delta; for (int e = frm[T]; e; e = frm[st[e]])
        fl = min(fl, cap[e]); delta = dis[T] * fl;
    if (sum + delta >= 0) {
        sum += delta; ans += fl;
        for (int e = frm[T]; e; e = frm[st[e]])
            cap[e] -= fl, cap[e ^ 1] += fl; return 1;
    }
    else return ans += sum / (-dis[T]), 0;
}
ll solve() {
    while (spfa() && add()); return ans;
}
int main() {
    int i, j; n = read(); for (i = 1; i <= n; i++) a[i] = read();
    for (i = 1; i <= n; i++) b[i] = read();
    for (i = 1; i <= n; i++) c[i] = read(); S = 1; T = n + 2;
    for (i = 1; i <= n; i++) cnt[i] = sigma(a[i]);
    for (i = 1; i <= n; i++) if (cnt[i] & 1) add_edge(S, i + 1, b[i], 0);
        else add_edge(i + 1, T, b[i], 0);
    for (i = 1; i <= n; i++) if (cnt[i] & 1) for (j = 1; j <= n; j++)
        if ((cnt[i] + 1 == cnt[j] && a[j] % a[i] == 0) ||
            (cnt[j] + 1 == cnt[i] && a[i] % a[j] == 0))
                add_edge(i + 1, j + 1, INF, 1ll * c[i] * c[j]);
    cout << solve() << endl; return 0;
}