【Sdoi2016】数字配对

Source and Judge

Sdoi2016
Bzoj4514
Luogu4068
Loj2031

Problem

【Description】
有 n 种数字,第 i 种数字是 ai、有 bi 个,权值是 ci。
若两个数字 ai、aj 满足,ai 是 aj 的倍数,且 ai/aj 是一个质数,
那么这两个数字可以配对,并获得 ci×cj 的价值。
一个数字只能参与一次配对,可以不参与配对。
在获得的价值总和不小于 0 的前提下,求最多进行多少次配对。
【Input】
第一行一个整数 n。
第二行 n 个整数 a1、a2、……、an。
第三行 n 个整数 b1、b2、……、bn。
第四行 n 个整数 c1、c2、……、cn。
【Output】
一行一个数,最多进行多少次配对
【Limited conditions】
n≤200,ai≤10^9,bi≤10^5,|ci|≤10^5
【Sample input】
3
2 4 8
2 200 7
-1 -2 1
【Sample output】
4
【Sample explanation】

Record

1h

Analysis

请先思考后再展开

这道题有意思的地方不是构图

首先,对于(i,j),判断能否配对,直接枚举约数要sqrt(a),即使配上线筛也是非常慢的.
考虑条件的特性:多出一个质因数,因为前面有个条件限制着,完全可以看作质因数的幂之和+1
所以这个是可以在枚举外面预处理的,然后其实线筛是可以省去的,因为合数已经被前面的筛去了.

(st,i),cost=0,flow=b[i]
(i,j),cost=c[i]*c[j],flow=INF
(i,ed),cost=0,flow=b[i]
然后跑一下最大费用最大流
其实会不会有种杀鸡用牛刀的感觉,毕竟很简单

然而最关键的地方在于,这个权值和不能是负数,
那么当有一天我们跑出来的最长路乘上哪怕1的流量,已经会导致答案变负数了,显然game over
还有一种情况是最长路是负数,那么就要限制一下流量,确保费用是非负数即可.

然后网上有人还要分奇偶,那根本就不是正常人的思维,其实答案直接除二就好,
否则显然分配方案不对称的话不会使结果更优.

Code

请先思考后再展开
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
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
//*******************全局常量*******************
const int MAXN=410,MAXM=80000;
//*******************全局定义*******************
typedef long long ll;
const ll INF=(1ll<<60);
int hou[MAXN];
bool v[MAXN];
struct Edge
{
int y,g,oth;
ll w,c;
}e[MAXM];
int ln=0;
void ins(int x,int y,ll w,ll c)
{
e[++ln]=(Edge){y,hou[x],ln+1,w,c};hou[x]=ln;
e[++ln]=(Edge){x,hou[y],ln-1,-w,0};hou[y]=ln;
}
ll mymax(ll x,ll y) {return x>y?x:y;}
ll mymin(ll x,ll y) {return x<y?x:y;}
//*******************实现*******************
int st,ed;
int lrd[MAXN];
ll dis[MAXN],mic[MAXN];
queue<int> lst;
ll now=0,ans=0;
bool bfs()
{
memset(dis,-63,sizeof(dis));
memset(v,0,sizeof(v));
lst.push(st);dis[st]=0;v[st]=1;mic[st]=INF;
while(!lst.empty())
{
int x=lst.front();lst.pop();
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(dis[y]<dis[x]+e[k].w and e[k].c>0)
{
dis[y]=dis[x]+e[k].w;
mic[y]=mymin(mic[x],e[k].c);
lrd[y]=e[k].oth;
if(!v[y]) v[y]=1,lst.push(y);
}
}
v[x]=0;
}
if(mic[ed]==0) return 0;
ll cost=dis[ed],flow=mic[ed];
if(cost<-now) return 0;//game over
if(cost<0) flow=mymin(flow,-now/cost);
now+=flow*cost;
ans+=flow;
for(int x=ed;x!=st;x=e[lrd[x]].y)
{
e[e[lrd[x]].oth].c-=flow;
e[lrd[x]].c+=flow;
}
return 1;
}
//*******************主函数*******************
int get(int x)
{
int s=0;
for(int i=2;i*i<=x;i++) {while(x%i==0) x/=i,s++;}
if(x>1) s++;
return s;
}
int a[MAXN],b[MAXN];ll c[MAXN];
int cnt[MAXN];
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),cnt[i]=get(a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
st=0,ed=2*n+1;
for(int i=1;i<=n;i++)
{
ins(st,i,0,b[i]);ins(n+i,ed,0,b[i]);
for(int j=1;j<i;j++)
{
if(
((a[i]%a[j])==0 and cnt[i]==cnt[j]+1) or
((a[j]%a[i])==0 and cnt[j]==cnt[i]+1)
)
{
ins(i,n+j,c[i]*c[j],INF);
ins(j,n+i,c[i]*c[j],INF);
}
}
}
while(bfs()) ;
printf("%lld\n",ans/2);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/数字配对.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%