BZOJ 4514 费用流

思路：

懒得写了

http://blog.csdn.net/werkeytom_ftd/article/details/51277482

//By SiriusRen

#include <queue>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define int long long

#define mem(x,y) memset(x,y,sizeof(x))

const int M=,N=,inf=1000000000000000ll;

int n,a[M],b[M],c[M],f[M],jy,T,ans1,ans2;

int edge[N],cost[N],v[N],next[N],first[M];

int with[M],vis[M],minn[M],dis[M],tot;

void Add(int x,int y,int C,int E){edge[tot]=E,cost[tot]=C,v[tot]=y,next[tot]=first[x],first[x]=tot++;}

void add(int x,int y,int C,int E){Add(x,y,C,E),Add(y,x,-C,);}

bool tell(){

    mem(vis,),mem(minn,0x3f),mem(dis,0x3f);

    queue<int>q;q.push(),dis[]=;

    while(!q.empty()){

        int t=q.front();q.pop(),vis[t]=;

        for(int i=first[t];~i;i=next[i])

            if(dis[v[i]]>dis[t]+cost[i]&&edge[i]){

                dis[v[i]]=dis[t]+cost[i],minn[v[i]]=min(minn[t],edge[i]),with[v[i]]=i;

                if(!vis[v[i]])vis[v[i]]=,q.push(v[i]);

            }

    }return dis[T]<=10000000000000000ll;

}

void zeng(){

    for(int i=T;i;i=v[with[i]^])edge[with[i]]-=minn[T],edge[with[i]^]+=minn[T];

    ans1+=dis[T]*minn[T];ans2+=minn[T];

}

signed main(){

    mem(first,-);

    scanf("%lld",&n),T=n+;

    for(int i=;i<=n;i++){

        scanf("%lld",&a[i]),jy=a[i];

        int sqr=sqrt(jy);

        for(int j=;j<=sqr;j++)

            while(jy%j==)jy/=j,f[i]++;

        if(jy!=)f[i]++;

    }

    for(int i=;i<=n;i++)scanf("%lld",&b[i]),f[i]&?add(,i,,b[i]):add(i,T,,b[i]);

    for(int i=;i<=n;i++)scanf("%lld",&c[i]);

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            if(a[i]&&a[j]&&abs(f[j]-f[i])==&&a[i]%a[j]==)

                add((f[i]&)?i:j,(f[i]&)?j:i,-c[i]*c[j],inf);

    while(tell()){zeng();if(ans1>){if(dis[T])ans2-=(ans1+dis[T]-)/dis[T];printf("%lld\n",ans2);return ;}}

    printf("%lld\n",ans2);

}