BZOJ4514【SDOI2016】数字配对 <费用流>

Problem

【SDOI2016】数字配对

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

有 $n$ 种数字，第 $i$ 种数字是 $a_i$、有 $b_i$ 个，权值是 $c_i$。
若两个数字 $a_i,\ a_j$ 满足，$a_i$ 是 $a_j$ 的倍数，且 $\frac{a_i}{a_j}$ 是一个质数，那么这两个数字可以配对，并获得 $c_i\times c_j$ 的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于 $0$ 的前提下，求最多进行多少次配对。

Input

第一行一个整数 $n$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。
第三行 $n$ 个整数$b_1,b_2,\cdots,b_n$。
第四行 $n$ 个整数 $c_1,c_2,\cdots,c_n$。

Output

一行一个数，最多进行多少次配对

Sample Input

3
2 4 8
2 200 7
-1 -2 1

Sample Output

4

HINT

$n\le 200，a_i\le 10^9，b_i\le 10^5，∣c_i∣\le 10^5$

标签：费用流

Solution

比较难想的二分图建模。
记$f(x)$为$x$分解质因数后的项数（$4=2\times 2$算两项），$\frac{a_i}{a_j}$为质数的充要条件为$f(x)=f(y)+1且y|x$。
可知$f(x)$奇偶性相同的一定不能配对，所以可建二分图，$f(x)$为奇在一边，$f(x)$为偶在另一边。
两边间连边则看是否有整除条件，流量为$INF$，费用为$c_i\times c_j$。
把每个点拆成左右两个点，左边与源点相连，右边与汇点相连，容量为 $b_i$，费用为零。
跑费用流每增广一次就判一下是否费用小于 $0$，注意最后退出的时候不要把新加入的流全退完，退一部分至刚好大于等于$0$即可。

Code

#include <bits/stdc++.h>
#define MAX_N 300
#define MAX_M 50000
#define INF 1e16
using namespace std;
typedef long long lnt;
int n, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5];    lnt mxf, cur;
int a[MAX_N+5], f[MAX_N+5];    lnt b[MAX_N+5], c[MAX_N+5];
struct node {int v, nxt; lnt c, w;} E[MAX_M+5];
void init() {s = 0, t = n+1, memset(pr, -1, sizeof pr);}
void insert(int u, int v, lnt c, lnt w) {E[cnt] = (node){v, pr[u], c, w}, pr[u] = cnt++;}
void addedge(int u, int v, lnt c, lnt w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5], mrk[MAX_N+5];	lnt d[MAX_N+5];	int cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(cr, -1, sizeof cr), memset(d, 0, sizeof d);
    memset(mrk, false, sizeof mrk), d[s] = 0, que.push(s), inq[s] = true, mrk[s] = true;
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v;	lnt c = E[i].c, w = E[i].w;
            if (c && (!mrk[v] || d[u]+w > d[v])) {
                mrk[v] = true, d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (!mrk[t]) return false;	lnt flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, cur += d[t]*flow;
    if (cur < 0) {mxf -= cur%d[t] == 0 ? cur/d[t] : cur/d[t]+1; return false;}	return true;
}
int calc(int x) {
    int ret = 0;
    for (int i = 2; i <= x; i++)
        while (!(x%i)) x /= i, ret++;
    if (x^1) ret++;	return ret;
}
int main() {
    scanf("%d", &n), init();
    for (int i = 1; i <= n; i++) scanf("%d", a+i), f[i] = calc(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++) if (f[i]&1) addedge(s, i, b[i], 0); else addedge(i, t, b[i], 0);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
        if ((f[i]&1) && ((f[i] == f[j]+1 && a[i]%a[j] == 0) || (f[i]+1 == f[j] && a[j]%a[i] == 0)))
            addedge(i, j, INF, c[i]*c[j]);
    while (SPFA()) ;	return printf("%lld", mxf), 0;
}