有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数，那么这两个数字可以配对，并获得 ci×cj 的价值。一个数字只能参与一次配对，可以不参与配对。在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。
这道题如果取消那个总和不小于0的情况呢？然后我们发现可以用最大流做，就是把a[i]有奇数个质因子的连向源点，偶数个质因子连向汇点建边，跑个最大流就可以了，正确性？显然啊现在把总和不小于0的情况考虑进来，我们发现有费用了我们考虑跑最大费用最大流，那么由于每次增广的是一个较大的费用也就是说每次增广出来的费用是递减的这样我们就可以当cost<0时，输出答案这样有一个问题，就是说最后一次增广出来的流量是不能全部跑出来的，也许会跑出来一部分那么这一部分可以通过cost / -dis[t]这种方式求出来，于是问题完美的解决啦
#include <map>#include <set>#include <queue>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>using namespace std;#define LL long long#define llinf 2000000000000000000#define inf 2147483647#define for1(i, x, y) for(LL i = (x); i <= (y); i ++)#define for2(i, x, y) for(LL i = (x); i >= (y); i --)namespace mcmf{ LL s, t; struct Edge{ LL u, v, cap, flow; LL cost; LL next; } G[250010]; LL tot; LL head[3000]; LL inq[3000]; LL d[3000]; LL p[3000]; LL a[3000]; inline void init(){ memset(head, -1, sizeof(head)); tot = -1; } inline void add(LL u, LL v, LL w, LL cost){ G[++ tot] = (Edge){u, v, w, 0, cost, head[u]}; head[u] = tot; G[++ tot] = (Edge){v, u, 0, 0, -cost, head[v]}; head[v] = tot; return; } inline bool BellmanFord(LL& flow, LL& cost){ for(LL i = s; i <= t; i ++) d[i] = -llinf; memset(inq, 0, sizeof(inq)); d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = inf; queue<LL> Q; Q.push(s); while(!Q.empty()){ LL u = Q.front(); Q.pop(); inq[u] = 0; for(LL i = head[u]; i != -1; i = G[i].next){ Edge& e = G[i]; if(e.cap > e.flow && d[e.v] < d[u] + e.cost){ d[e.v] = d[u] + e.cost; p[e.v] = i; a[e.v] = min(a[u], e.cap - e.flow); if(!inq[e.v]){ Q.push(e.v); inq[e.v] = 1; } } } } if(d[t] == -llinf) return false; flow += a[t]; cost += d[t] * (LL)a[t]; if(cost < 0){ cost -= d[t] * (LL)a[t]; flow -= a[t]; flow += cost / -d[t]; return false; } LL u = t; while(u != s){ G[p[u]].flow += a[t]; G[p[u] ^ 1].flow -= a[t]; u = G[p[u]].u; } return true; } inline LL Minflow(){ LL flow = 0; LL cost = 0; while(BellmanFord(flow, cost)); return flow; }}LL a[100010], b[100010], c[100010];LL prime[100010], tot; bool vis[100010];LL cnta[100010];inline LL read(){ // getchar较快于scanf，更快的还有fread，不会23333 char ch = getchar(); LL x = 0, f = 1; while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x * f;} inline LL llread(){ char ch = getchar(); LL x = 0, f = 1; while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x * f;} inline void init_prime(){ for1(i, 2, 100000){ if(!vis[i]) prime[++ tot] = i; for1(j, 1, tot){ if(i * prime[j] > 100000) break; vis[i * prime[j]] = 1; if(i % prime[j] == 0) break; } }}inline bool is_prime(LL x){ if(x <= 100000) return 1 - vis[x]; LL t = sqrt(x); for1(i, 1, tot){ if(prime[i] > t) break; if(x % prime[i] == 0) return false; } return true;}int main(){ LL n = read(); for1(i, 1, n) a[i] = llread(); for1(i, 1, n) b[i] = llread(); for1(i, 1, n) c[i] = llread(); mcmf::init(); init_prime(); for1(i, 1, n){ LL t = sqrt(a[i]); LL o = a[i]; for1(j, 1, tot){ if(prime[j] > t) break; while(o % prime[j] == 0) o /= prime[j], cnta[i] ++; if(o == 1) break; } if(o != 1) cnta[i] ++; } mcmf::s = 0; mcmf::t = n + 1; for1(i, 1, n){ if(cnta[i] & 1) mcmf::add(0, i, b[i], 0); else mcmf::add(i, n + 1, b[i], 0); } for1(i, 1, n) if(cnta[i] & 1){ for1(j, 1, n) if(!(cnta[j] & 1)){ if(a[i] % a[j] != 0 && a[j] % a[i] != 0) continue; if(a[i] % a[j] == 0 && is_prime(a[i] / a[j])) mcmf::add(i, j, inf, c[i] * c[j]); else if(a[j] % a[i] == 0 && is_prime(a[j] / a[i])) mcmf::add(i, j, inf, c[i] * c[j]); } } printf("%lld", mcmf::Minflow()); return 0;}
