Reku
0%

BZOJ 4514 [Sdoi2016]数字配对

Posted on Edited on In , Views: Valine:

有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。 若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数， 那么这两个数字可以配对，并获得 ci×cj 的价值。 一个数字只能参与一次配对，可以不参与配对。 在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。

这个题基本一看就是费用流，但是建图比较厉害。 对于每一个\(a_i\)我们可以计算出来是由多少个质数组成的。这样我们就发现了一堆奇数个质数组成的数和偶数个组成的数。 对于每一种配对方法，我们都可以等价成一个从奇数个质数组成的数连到偶数个的质数组成的数流量为无穷，费用为\(-c[i] \times c[j]\)组成的边（因为我们使用最小费用流解决问题，所以所有的费用反向。） 这样显然就是个二分图模型！ 源点向奇数连流量为\(b_i\)，费用为\(0\)的边。 偶数向汇点连流量为\(b_i\)，费用为\(0\)的边。 然后网络流的终止条件就是到达不了汇点，或者\(cost \ge 0\)。第二个条件时，最后spfa发现的流量可能不会流满，需要判断一下。

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include<bits/stdc++.h>
#define maxn 1000
#define INF 222147483600ll
using namespace std;
struct Edge{
	long long from,to,cap,flow,cost;
};
struct MCMF{
	long long n,m,s,t;
	vector<Edge> edges;
	vector<long long> G[maxn];
	long long inq[maxn];
	long long d[maxn];
	long long p[maxn];
	long long a[maxn];
	
	void init(long long n){
		this->n=n;
		for(long long i=0;i<n;i++) G[i].clear();
		edges.clear();
	}
	
	void Addedge(long long from,long long to,long long cap,long long cost){
		edges.push_back((Edge){from,to,cap,0,cost});
		edges.push_back((Edge){to,from,0,0,-cost});
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	
	bool BellmanFord(long long s,long long t,long long &flow,long long &cost){
		for(int i=0;i<n;i++) d[i]=INF;
		memset(inq,0,sizeof(inq));
		d[s]=0; inq[s]=1; p[s]=0; a[s]=INF;
		//cout<<"********"<<endl;
		queue<long long> Q;
		Q.push(s);
		while(!Q.empty())
		{
			long long u=Q.front(); Q.pop();
			inq[u]=0;
			for(int i=0;i<G[u].size();i++)
			{
				Edge& e=edges[G[u][i]];
				if(e.cap>e.flow&&d[e.to]>d[u]+e.cost)
				{
					//cout<<e.from<<" "<<e.to<<" "<<e.cap<<" "<<e.flow<<" "<<e.cost<<endl;
					d[e.to]=d[u]+e.cost;
					p[e.to]=G[u][i];
					a[e.to]=min(a[u],e.cap-e.flow);
					if(!inq[e.to]) {
						Q.push(e.to);
						inq[e.to]=1;
					}
				}
			}
		}
		if(d[t]==INF) return false;
		if(cost+d[t]>0) return false;
		long long o=abs(cost)/d[t];
		if(d[t]>0) a[t]=min(a[t],o);
		flow+=a[t];
		cost+=d[t]*a[t];
		long long u=t;
		while(u!=s){
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
			u=edges[p[u]].from;
		}
		//system("pause");
		return true;
	}
	
	long long Mincost(long long s,long long t){
		long long flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost));
		printf("%lld\n",flow);
		return cost;
	}
} dinic;
bool u[32010]={};
vector<int> su;
void init()
{
	u[1]=1;
	for(int i=2;i<=32000;i++)
	{
		if(u[i]==0)
		{
			su.push_back(i);
			for(int j=2*i;j<=32000;j+=i)
			{
				u[j]=1;
			}
		}
	}
}
int n;
long long a[310];
long long b[310];
long long c[310];
long long p[310];
int main()
{
	init();
	scanf("%d",&n);
	dinic.init(n+2);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		int tt=a[i];
		int q=sqrt(a[i]);
		for(int j=2;j<=q;j++)
		{
			while(a[i]%j==0)
			{
				p[i]++;
				a[i]/=j;
			}
		}
		if(a[i]!=1) p[i]++;
		a[i]=tt;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&b[i]);
		if(p[i]%2==1)
		{
			dinic.Addedge(0,i,b[i],0);
		}
		else
		{
			dinic.Addedge(i,n+1,b[i],0);
		}
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&c[i]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[j]%a[i]==0)
			{
				int q=a[j]/a[i];
				bool bj=0;
				if(q==1) bj=1;
				for(int k=0;k<su.size();k++)
				{
					if(su[k]>=q) break;
					if(q%su[k]==0)
					{
						bj=1;
						break;
					}
				}
				if(bj==0)
				{
					if(p[i]%2==1)
					{
						dinic.Addedge(i,j,INF,-(c[i]*c[j]));
					}
					else
					{
						dinic.Addedge(j,i,INF,-(c[i]*c[j]));
					}
				}
			}
		}
	}
	dinic.Mincost(0,n+1);
	return 0;
}