题解【P4068 [SDOI2016]数字配对】

传送门

萌新刚学费用瘤，所以本篇题解会尽量讲得详细一些。

前置芝士：

• 最小费用最大流。
•  质因数分解。

设 $cnt_i$ 为 $a_i$ 质因数分解后各项指数之和。

那么 $a_i$ 和 $a_j$ 能匹配的条件为，$a_i\bmod a_j=0$ 且 $cnt_i=cnt_j+1$。

稍微解释一下，若 $a_i$ 是 $a_j$ 的倍数，那么 $a_i$ 肯定包含 $a_j$ 的所有质因数，而又有条件 $cnt_i=cnt_j+1$，说明 $a_i$ 在 $a_j$ 的基础上只多了一个质因数，所以 $\frac{a_i}{a_j}$ 是一个质数。

现在考虑建图，我们根据 $cnt$ 的奇偶性将 $a_i$ 分成两堆儿：$cnt_i$ 为奇数的放在左边，$cnt_i$ 为偶数的放在右边。

考虑到【一个数只能匹配一次】这一条件，我们把流量设成 $b_i$。

新建一个虚拟汇点 $s$，将 $s$ 与左边的每一个点连一条容量为 $b_i$，费用为 $0$ 的边。

新建一个虚拟汇点 $t$，将右边的每一个点与 $t$ 连一条容量为 $b_i$，费用为 $0$ 的边。

通过这样建图，就可以保证每一个 $a_i$ 最多使用 $b_i$ 次。

两边的点就暴力建图，对于两个可以匹配的点 $i,j$，连一条 从 $i$ 到 $j$，容量为 $\infty$，费用为 $c_i\times c_j$ 的边。

中间部分的建图就已经不用考虑 $b_i$ 的限制了，因为两边的连边都已经考虑在内了。所以容量设为无限大。

那么现在就只剩下【价值之和不小于 $0$】 这一条件了。

这就需要对费用流改动一下。

考虑贪心。我们每次用 SPFA 跑最长路，那么每次 SPFA 跑到终点的最长路肯定是下降的。

我们对于当前的这一条增光路，在价值和不小于 $0$ 的情况下尽可能多的添加流量，直到价值和小于 $0$。

坑点：开 long long，边数组别开小。

贴一下巨丑的代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int MAXN(210);
const ll INF(1e18);
int n,a[MAXN],b[MAXN];
ll c[MAXN];
int cnt[MAXN];
int s,t;
inline ll Min(ll x,ll y){return x1) ++res;
	return res;
}
struct E{int to,nxt;ll cost,flow;};
E edge[MAXN*MAXN];
int head[MAXN],tot=1;
inline void add_edge(int u,int v,ll f,ll w)
{
	edge[++tot].nxt=head[u];
	head[u]=tot;
	edge[tot].to=v;
	edge[tot].flow=f;
	edge[tot].cost=w;
	return;
}
ll dis[MAXN],flow[MAXN],Cost,Flow;
int pre[MAXN],pos[MAXN];
bool inq[MAXN];
queueq;
inline bool SPFA()
{
	for(register int i=s;i<=t;i++)
		dis[i]=-INF,flow[i]=INF,inq[i]=false;
	q.push(s);
	dis[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		inq[u]=false;
		for(register int i=head[u];i;i=edge[i].nxt)
		{
			E e=edge[i];
			if(dis[e.to]-INF;
}
inline bool MCMF()
{
	if(!SPFA()) return false;
	ll now=dis[t]*flow[t];
	if(Cost+now>=0)
	{
		Cost+=now;
		Flow+=flow[t];
		for(register int u=t;u!=s;u=pre[u])
		{
			int p=pos[u];
			edge[p].flow-=flow[t];
			edge[p^1].flow+=flow[t];
		}
		return true;
	}
	else return Flow+=Cost/(-dis[t]),false;	
}
int main()
{
	scanf("%d",&n);
	s=0,t=n+1;
	for(register int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(register int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(register int i=1;i<=n;i++) scanf("%lld",&c[i]);
	for(register int i=1;i<=n;i++) cnt[i]=fenjie(a[i]);
	for(register int i=1;i<=n;i++)
		if(cnt[i]&1) add_edge(s,i,b[i],0),add_edge(i,s,0,0);
		else add_edge(i,t,b[i],0),add_edge(t,i,0,0);
	for(register int i=1;i<=n;i++) if(cnt[i]&1)
		for(register int j=1;j<=n;j++)
			if((a[i]%a[j]==0&&cnt[i]==cnt[j]+1)||(a[j]%a[i]==0&&cnt[j]==cnt[i]+1))
				add_edge(i,j,INF,c[i]*c[j]),add_edge(j,i,0,-c[i]*c[j]);
	while(MCMF());
	printf("%lld\n",Flow);
	return 0;
}

$$\texttt{The End.by UF}$$