[題目連結]
https://www.lydsy.com/JudgeOnline/problem.php?id=4514
[算法]
記Cnti表示第i個數的質因子次數之和
那麼i與j可以配對當且僅當 : Cnti = Cntj + 1且ai為aj的倍數或Cntj = Cnti + 1且aj為ai的倍數
那麼Cnti為奇數與Cnti為偶數的點構成了兩個集合
考慮費用流 :
将源點與Cnti為奇數的點連一條容量為bi , 費用為0的邊
将Cnti為偶數的點向彙點連一條容量為bi , 費用為0的邊
對于所有可以配對的(i , j) , 将i與j連一條容量為正無窮 , 費用為CiCj的邊
答案即為這張圖的最大費用最大流
但注意由于題目中要求費用為非負數 , 是以可以考慮貪心 :
由于最大費用最大流每次找到的增廣路的費用單調遞減 , 是以優先考慮費用大的
時間複雜度 : O(Costflow(N , N ^ 2))
#include<bits/stdc++.h>
using namespace std;
#define N 520
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll inf = 1e18;
struct edge
{
int to;
ll w , cost;
int nxt;
} e[N * N * 4];
int n , tot , S , T;
ll sum , ans;
int a[N] , b[N] , c[N] , cnt[N] , pre[N] , head[N];
ll dist[N] , incf[N];
bool inq[N];
template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = 1; x = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
x *= f;
}
inline void addedge(int u , int v , ll w , ll cost)
{
++tot;
e[tot] = (edge){v , w , cost , head[u]};
head[u] = tot;
++tot;
e[tot] = (edge){u , 0 , -cost , head[v]};
head[v] = tot;
}
inline int get(int x)
{
int ret = 0;
for (int i = 2; i <= sqrt(x); i++)
{
while (x % i == 0)
{
x /= i;
++ret;
}
}
if (x > 1) ++ret;
return ret;
}
inline bool spfa()
{
queue< int > q;
for (int i = 1; i <= T; i++)
{
inq[i] = false;
dist[i] = -inf;
incf[i] = inf;
}
pre[S] = 0;
inq[S] = true;
dist[S] = 0;
incf[S] = inf;
q.push(S);
while (!q.empty())
{
int cur = q.front();
q.pop();
inq[cur] = false;
for (int i = head[cur]; i; i = e[i].nxt)
{
int v = e[i].to;
ll w = e[i].w , cst = e[i].cost;
if (w > 0 && dist[cur] + cst > dist[v])
{
dist[v] = dist[cur] + cst;
incf[v] = min(incf[cur] , w);
pre[v] = i;
if (!inq[v])
{
inq[v] = true;
q.push(v);
}
}
}
}
if (dist[T] != -inf) return true;
else return false;
}
inline bool update()
{
if (sum + dist[T] * incf[T] >= 0)
{
sum += dist[T] * incf[T];
ans += incf[T];
int now = T;
while (pre[now])
{
e[pre[now]].w -= incf[T];
e[pre[now] ^ 1].w += incf[T];
now = e[pre[now] ^ 1].to;
}
return true;
} else
{
ans += sum / (-dist[T]);
return false;
}
}
int main()
{
read(n);
tot = 1;
for (int i = 1; i <= n; i++) read(a[i]);
for (int i = 1; i <= n; i++) read(b[i]);
for (int i = 1; i <= n; i++) read(c[i]);
for (int i = 1; i <= n; i++) cnt[i] = get(a[i]);
S = n + 1 , T = S + 1;
for (int i = 1; i <= n; i++)
if (cnt[i] & 1) addedge(S , i , b[i] , 0);
else addedge(i , T , b[i] , 0);
for (int i = 1; i <= n; i++)
{
if (cnt[i] & 1)
{
for (int j = 1; j <= n; j++)
{
if (((a[j] % a[i] == 0) && (cnt[j] == cnt[i] + 1)) || ((a[i] % a[j] == 0) && (cnt[i] == cnt[j] + 1)))
addedge(i , j , inf , 1ll * c[i] * c[j]);
}
}
}
while (spfa() && update());
printf("%lld\n" , ans);
return 0;
}