4514: [Sdoi2016]数字配对
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1870 Solved: 712
[Submit][Status][Discuss]
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
一行一个数，最多进行多少次配对
Sample Input
3
2 4 8
2 200 7
-1 -2 1
Sample Output
4
HINT
n≤200，ai≤10^9，bi≤10^5，∣ci∣≤10^5
emmm
每种数字看成点，拆点为xi，yi
S向xi连容量bi费用0的边，yi向T连容量bi费用0的边
如果两种数字u，v可以配对xu连yv，yu连xv容量均为inf，费用均为cu*cv
贪心跑最大费用，直到跑出来的费用为负，特判一波break掉
注意longlong
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#define inf 0x3f3f3f3f
#define ll long long
#define N 405
using namespace std;
int n,m,tot,S,T,flow,hd[N],pre[N],a[N],vis[N];
ll cost,d[N];
struct edge{int u,v,next,cap;ll w;}e[N*N*2];
void adde(int u,int v,ll w,int c){
e[tot].v=v;
e[tot].u=u;
e[tot].w=w;
e[tot].next=hd[u];
e[tot].cap=c;
hd[u]=tot++;
}
struct ele{int a,b,c;}p[N];
bool cmp(ele a,ele b){return a.a>b.a;}
bool judge(int x){
int y=sqrt(x);
if(x<=1)return 0;
for(int i=2;i<=y;i++)
if(!(x%i))return 0;
return 1;
}
bool spfa(){
queue<int>q;ll t=(ll)inf*inf;
for(int i=S;i<=T;i++)d[i]=-t;d[S]=0;
memset(pre,-1,sizeof(pre));a[S]=1<<30;
q.push(S);
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
for(int i=hd[u];~i;i=e[i].next){
int v=e[i].v;
if(e[i].cap&&d[v]<d[u]+e[i].w){
d[v]=d[u]+e[i].w;
pre[v]=i;
a[v]=min(a[u],e[i].cap);
if(vis[v])continue;
vis[v]=1;q.push(v);
}
}
}
if(d[T]==-t)return 0;
ll tmp=a[T]*d[T];
if(cost+tmp<0){
ll res=cost/d[T];
flow-=(int)res;
return 0;
}
flow+=a[T];cost+=(ll)a[T]*d[T];
int u=T;
while(u!=S){
e[pre[u]].cap-=a[T];
e[pre[u]^1].cap+=a[T];
u=e[pre[u]].u;
}
return 1;
}
int main(){
#ifdef wsy
freopen("pair4.in","r",stdin);
#else
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
#endif
memset(hd,-1,sizeof(hd));
scanf("%d",&n);
S=0;T=n*2+1;
for(int i=1;i<=n;i++)scanf("%d",&p[i].a);
for(int i=1;i<=n;i++)scanf("%d",&p[i].b);
for(int i=1;i<=n;i++)scanf("%d",&p[i].c);
sort(p+1,p+1+n,cmp);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
if(p[i].a%p[j].a)continue;
if(!judge(p[i].a/p[j].a))continue;
adde(i,j+n,(ll)p[i].c*p[j].c,inf);
adde(j+n,i,(ll)p[i].c*p[j].c*(-1),0);
adde(j,i+n,(ll)p[i].c*p[j].c,inf);
adde(i+n,j,(ll)p[i].c*p[j].c*(-1),0);
}
for(int i=1;i<=n;i++){
adde(S,i,0,p[i].b);
adde(i,S,0,0);
adde(i+n,T,0,p[i].b);
adde(T,i+n,0,0);
}
while(spfa());
printf("%d",flow/2);
return 0;
}