4514: [Sdoi2016]数字配对

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1305 Solved: 498
[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

HINT

n≤200，ai≤10^9，bi≤10^5，∣ci∣≤10^5

Source

鸣谢Menci上传

当时一眼看出此题是费用流，建图很明显。//具体见代码

显然ans=maxflow;
然，碍于“在获得的价值总和不小于 0 的前提下”这个条件，只打了一个暴力。QAQ

#include<cstdio>
#include<cstdlib>
#include<iostream>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
typedef long long i64;
const int N=4005;
const int M=5e5+5;
const i64 inf=10000000000000LL;//一定要够大 
struct edge{int v,next;i64 cap,cost;}e[M];int tot=1,head[N];
int n,m,S,T,q[N],prev[N];bool vis[N];
i64 a[N],b[N],c[N];
i64 answ,ansf,dis[N];
void add(int x,int y,i64 z,i64 cost){
    e[++tot].v=y;e[tot].cap=z;e[tot].cost=cost;e[tot].next=head[x];head[x]=tot;
    e[++tot].v=x;e[tot].cap=0;e[tot].cost=-cost;e[tot].next=head[y];head[y]=tot;
}
bool spfa(){//非负费用最大流贪心流一定是正确的
    for(int i=S;i<=T;i++) vis[i]=0,dis[i]=-inf;
    unsigned short h=0,t=1;q[t]=S;dis[S]=0;
    while(h!=t){
        int x=q[++h];vis[x]=0;
        for(int i=head[x];i;i=e[i].next){
            if(e[i].cap&&dis[e[i].v]<dis[x]+e[i].cost){
                dis[e[i].v]=dis[x]+e[i].cost;
                prev[e[i].v]=i;
                if(!vis[e[i].v]){
                    vis[e[i].v]=1;//SLF优化还比朴素慢
                    //if(dis[e[i].v]>dis[x]){ 
                    //    q[h--]=e[i].v;
                    //}
                    //else{
                        q[++t]=e[i].v;
                    //}
                }
            }
        }
    }
    return answ+dis[T]>=0;//费用为非负的极限    
}
void augment(){
    i64 flow=inf;
    if(dis[T]<0) flow=answ/(-dis[T]);
    for(int i=T;i!=S;i=e[prev[i]^1].v){
        flow=min(flow,e[prev[i]].cap);
    }
    for(int i=T;i!=S;i=e[prev[i]^1].v){
        e[prev[i]].cap-=flow;
        e[prev[i]^1].cap+=flow;
    }
    ansf+=flow;
    answ+=flow*dis[T];
}
i64 fpow(i64 a,i64 p,i64 mod){
    i64 res=1;
    for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod;
    return res;
}
bool judge(i64 x){
    if(x<2) return 0;
    if(x==2) return 1;
    if(x&1^1) return 0;
    i64 a,t;
    for(int i=1;i<=10;i++){
        a=rand()%M;
        if(a>=x&&a%x==0) continue;
        t=fpow(a,x-1,x);
        if(t!=1) return 0;
    } 
    return 1;
}
int main(){
    scanf("%d",&n);S=0,T=n<<1|1;
    for(int i=1;i<=n;i++) scanf(LL,&a[i]);
    for(int i=1;i<=n;i++){
        scanf(LL,&b[i]);
        add(S,i,b[i],0);
        add(i+n,T,b[i],0);
    }
    for(int i=1;i<=n;i++) scanf(LL,&c[i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) continue;//暴力建图 
            if(a[j]&&!(a[i]%a[j])&&judge(a[i]/a[j])){
                add(i,j+n,inf,c[i]*c[j]);
            }
            if(a[i]&&!(a[j]%a[i])&&judge(a[j]/a[i])){
                add(i,j+n,inf,c[i]*c[j]);
            }
        }
    }
    while(spfa()) augment();
    printf(LL,ansf/2);
    return 0;
}