bzoj 4514 数字配对

Posted on | Views:

费用流.

  • 将每个数字 $a_i$ 拆成入点 $p_i$ 和出点 $q_i$,对于 $S\to p_i,q_i\to T$ 连费用为 $0$ ,容量为 $b_i$ 的边.
  • 若 $a_i,a_j$ 之间可以配对,就对于 $p_i\to q_j,p_j\to q_i$ 连费用为 $-c_i\cdot c_j$ ,容量为 $inf$ 的边.
  • 跑 $mcmf$ ,每次 $spfa$ 完之后判一下是否会使得费用 $>0$ ,若会,就加上限制下的最大流量,然后退出即可.

这样做每对的贡献都被算了 $2$ 次,所以最后答案要 $/2$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
const ll inf=1e18;
int head[MAXN],ecnt=-1,pcnt=0;
struct Edge
{
	int to,nx;
	ll flow,val;
}E[MAXN];
void addedge(int u,int v,ll flow,ll val)
{
	++ecnt;
	E[ecnt].to=v;
	E[ecnt].nx=head[u];
	E[ecnt].flow=flow;
	E[ecnt].val=val;
	head[u]=ecnt;
}
void ins(int u,int v,ll flow,ll val)
{
	addedge(u,v,flow,val);
	addedge(v,u,0,-val);
}
int n,a[MAXN],b[MAXN],c[MAXN];
int p[MAXN],q[MAXN];
bool is_prime(int x)
{
	if(x==1)
		return false;
	for(int i=2;i*i<=x;++i)
		if(x%i==0)
			return false;
	return true;
}
int vis[MAXN],pre[MAXN],lst[MAXN];
ll dis[MAXN],flow[MAXN];
bool spfa(int S,int T)
{
	for(int i=1;i<=pcnt;++i)
		dis[i]=inf,flow[i]=inf,vis[i]=0;
	pre[T]=-1;
	queue<int> q;
	dis[S]=0;
	vis[S]=1;
	q.push(S);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i!=-1;i=E[i].nx)
		{
			int v=E[i].to;
			if(E[i].flow>0 && dis[v]-dis[u]>E[i].val)
			{
				dis[v]=dis[u]+E[i].val;
				pre[v]=u;
				lst[v]=i;
				flow[v]=min(flow[u],E[i].flow);
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return pre[T]!=-1;
}
ll mcmf(int S,int T)
{
	ll maxflow=0,mincost=0;
	while(spfa(S,T))
	{
		if(mincost+flow[T]*dis[T]>0)
		{
			ll tmp=-mincost;
			maxflow+=tmp/dis[T];
			return maxflow;
		}
		maxflow+=flow[T];
		mincost+=flow[T]*dis[T];
		int now=T;
		while(now!=S)
		{
			E[lst[now]].flow-=flow[T];
			E[lst[now]^1].flow+=flow[T];
			now=pre[now];
		}
	}
	return maxflow;
}
int main()
{
	memset(head,-1,sizeof head);
	int S=++pcnt,T=++pcnt;
	n=read();
	for(int i=1;i<=n;++i)
		p[i]=++pcnt,q[i]=++pcnt;
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=n;++i)
	{
		b[i]=read();
		ins(S,p[i],b[i],0);
		ins(q[i],T,b[i],0);
	}	
	for(int i=1;i<=n;++i)
		c[i]=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<i;++j)
		{
			int x=max(a[i],a[j]),y=min(a[i],a[j]);
			if(x%y==0 && is_prime(x/y))
			{
				ins(p[i],q[j],inf,-1LL*c[i]*c[j]);
				ins(p[j],q[i],inf,-1LL*c[i]*c[j]);
			}
		}
	int ans=mcmf(S,T);
	cout<<ans/2<<endl;
	return 0;
}