bzoj 4514 [Sdoi2016]数字配对

Posted by

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=4514

题解

首先考虑怎么建图,可以发现将不同数字质因数分解后,可以按质因数数量的奇偶来分成两部,容易发现这是一个二分图;

假设质因数数量位奇的数在\(X\)部,其余的在\(Y\)部:

从源点向\(X\)部每个节点\(i\)连边,容量为\(b[i]\),费用为\(0\),从\(Y\)部每个节点\(j\)向汇点连边,容量为\(b[j]\),费用为\(0\);

如果两个数\(i,j\)满足题目中的条件,在\(i,j\)之间连边,容量为\(INF\),费用为\(c[i]\times c[j]\),注意要从\(X\)部向\(Y\)部连边;

这时候用EK算法跑最大费用最大流,首先增广的一定是费用最大的路径,当增广到某条路径使得费用小于\(0\)时,停止增广,输出流量即可。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注