一行一个数，最多进行多少次配对

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

鸣谢Menci上传

#include<cstdio>#include<cstdlib>#include<iostream>#ifdef WIN32#define LL "%I64d"#else#define LL "%lld"#endifusing 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;}