BZOJ4514 [Sdoi2016]数字配对【费用流】

题目

有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。

若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数，

那么这两个数字可以配对，并获得 ci×cj 的价值。

一个数字只能参与一次配对，可以不参与配对。

在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。

输入格式

第一行一个整数 n。

第二行 n 个整数 a1、a2、……、an。

第三行 n 个整数 b1、b2、……、bn。

第四行 n 个整数 c1、c2、……、cn。

输出格式

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

输入样例

2 4 8

2 200 7

-1 -2 1

输出样例

提示

n≤200，ai≤10^9，bi≤105，∣ci∣≤10^5

题解

如果\(a_i\)和\(a_j\)之间相差一个质数，那么它们一定是互为倍数关系且质因子分解后指数和只相差\(1\)

容易发现，相互匹配的两个数的指数和一定是一奇一偶

所以这是一个二分图匹配问题

用最大费用最大流实现匹配即可

但由于费用和非负，我们在最大流统计流量时，如果当前答案加上本次新增费用小于0，就刚好取到不小于0的部分

由于先取大的一定比取小的好，所以这样的贪心策略正确

#include<iostream>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

#include<algorithm>

#define LL long long int

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");

using namespace std;

const int maxn = 205,maxm = 200005;

const LL INF = 1000000000000000000ll;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int n,ans;

LL a[maxn],b[maxn],c[maxn],cnt[maxn],sum;

LL d[maxn],minf[maxn];

int p[maxn];

int h[maxn],ne = 2,S,T;

struct EDGE{int to,nxt; LL f,w;}ed[maxm];

inline void build(int u,int v,LL f,LL w){

	ed[ne] = (EDGE){v,h[u],f,w}; h[u] = ne++;

	ed[ne] = (EDGE){u,h[v],0,-w}; h[v] = ne++;

}

void Sp(int u){

	int x = a[u];

	for (int i = 2; i <= x; i++)

		if (x % i == 0){

			while (x % i == 0) cnt[u]++,x /= i;

		}

	if (x - 1) cnt[u]++;

}

queue<int> q;

int inq[maxn];

void mincost(){

	while (true){

		for (int i = S; i <= T; i++) inq[i] = p[i] = 0,d[i] = INF;

		q.push(S); d[S] = 0; minf[S] = INF;

		int u;

		while (!q.empty()){

			u = q.front(); q.pop();

			inq[u] = false;

			Redge(u) if (ed[k].f && d[to = ed[k].to] > d[u] + ed[k].w){

				d[to] = d[u] + ed[k].w; minf[to] = min(minf[u],ed[k].f);

				p[to] = k;

				if (!inq[to]) q.push(to),inq[to] = true;

			}

		}

		if (d[T] == INF) return;

		if (d[T] <= 0){

			sum += -d[T] * minf[T];

			ans += minf[T];

			u = T;

			while (u != S){

				ed[p[u]].f -= minf[T];

				ed[p[u] ^ 1].f += minf[T];

				u = ed[p[u] ^ 1].to;

			}

		}

		else {

			int l = min(minf[T],sum / d[T]);

			if (!l) return;

			sum += -d[T] * l;

			ans += l;

			u = T;

			while (u != S){

				ed[p[u]].f -= l;

				ed[p[u] ^ 1].f += l;

				u = ed[p[u] ^ 1].to;

			}

		}

	}

}

int main(){

	n = read(); S = 0; T = n + 1;

	REP(i,n) a[i] = read(),Sp(i);

	REP(i,n){

		b[i] = read();

		if (cnt[i] & 1) build(S,i,b[i],0);

		else build(i,T,b[i],0);

	}

	REP(i,n) c[i] = read();

	REP(i,n) REP(j,n){

		if ((cnt[i] & 1) && !(cnt[j] & 1) && ((a[i] % a[j] == 0 && cnt[i] == cnt[j] + 1) || (a[j] % a[i] == 0 && cnt[j] == cnt[i] + 1))){

			build(i,j,INF,-(c[i] * c[j]));

		}

	}

	mincost();

	printf("%d\n",ans);

	return 0;

}

巴特西

BZOJ4514 [Sdoi2016]数字配对【费用流】

题目

输入格式

输出格式

输入样例

输出样例

提示

题解

最新文章

热门文章

巴特西

BZOJ4514 [Sdoi2016]数字配对 【费用流】

题目

输入格式

输出格式

输入样例

输出样例

提示

题解

最新文章

热门文章

BZOJ4514 [Sdoi2016]数字配对【费用流】