题解 P4068 【[SDOI2016]数字配对】
xyz32768
·
·
题解
分析题目，发现重点在于条件「一个数字只能参与一次配对」。
考虑求出cnt_i，表示a_i分解质因数之后，每个质因数的指数之和。
那么a_i和a_j能配对的条件转化为：
考虑一个二分图的模型。先按照$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$，则已经传输的总流量就是答案。
代码：
```cpp
#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;
}
```