4514: [Sdoi2016]数字配对 费用流

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=4514

思路

EK直接贪心做
<0的时候加上剩余返回
二分图a->b的时候
把b->a也连接上
最后除2
整除和贪心可只知道它是对的

代码

#include <bits/stdc++.h>
#define ll long long
#define iter vector<int>::iterator
using namespace std;
const ll N=5e5+7;
ll read() {
    ll x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
ll n,S,T,a[2007],b[2007],c[2007];
struct node {
    ll u,v,nxt,cap,cost;
}e[N<<1];
ll head[N<<1],tot=1;
void add_edge(ll u,ll v,ll cap,ll cost) {
    e[++tot].v=v;
    e[tot].u=u;
    e[tot].cap=cap;
    e[tot].cost=cost;
    e[tot].nxt=head[u];
    head[u]=tot;
}
void Add(ll u,ll v,ll cap,ll cost) {
//  cout<<u<<" "<<v<<"\n";
    add_edge(u,v,cap,cost);
    add_edge(v,u,0,-cost);
}
ll dis[N];
ll vis[N],frm[N];
bool spfa() {
    memset(dis,-0x3f,sizeof(dis));
    memset(vis,0,sizeof(dis));
    queue<int> q;
    q.push(S);
    dis[S]=0;
    while(!q.empty()) {
        ll u=q.front();
        q.pop();
        vis[u]=0;
        for(ll i=head[u];i;i=e[i].nxt) {
            ll v=e[i].v;
            if(e[i].cap&&dis[v]<dis[u]+e[i].cost) {
                dis[v]=dis[u]+e[i].cost;
                frm[v]=i;
                if(!vis[v]) {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return dis[T]>=-0x3f3f3f3f3f3f3f;
}
ll EK() {
    ll flow=0,ans=0;
    while(spfa()) {
        ll now_flow=0x3f3f3f3f;
        for(ll i=frm[T];i;i=frm[e[i].u])
            now_flow=min(now_flow,(ll)e[i].cap);
        for(ll i=frm[T];i;i=frm[e[i].u]) {
            e[i].cap-=now_flow;
            e[i^1].cap+=now_flow;
        }
        if(ans+1LL*now_flow*dis[T]<0) {
            ll ok=ans/-dis[T];
            return flow+ok;
        } else 
        ans+=now_flow*dis[T],flow+=now_flow;
    }
    return flow;
}
set<int> dsr[250];
int main() {
    freopen("a.in","r",stdin);
    n=read();
    for(ll i=1;i<=n;++i) a[i]=read();
    for(ll i=1;i<=n;++i) b[i]=read();
    for(ll i=1;i<=n;++i) c[i]=read();
    S=1001,T=1002;
    for(ll i=1;i<=n;++i) {
        ll tmp=a[i];
        for(ll j=2;j*j<=tmp;++j) {
            if(tmp%j==0) dsr[i].insert(j);
            while(tmp%j==0) tmp/=j;
        }
        if(tmp!=1) dsr[i].insert(tmp);
    }
    for(ll i=1;i<=n;++i) Add(S,i,b[i],0);
    for(ll i=1;i<=n;++i) Add(i+n,T,b[i],0);
    for(ll i=1;i<=n;++i) {
        for(ll j=i+1;j<=n;++j) {
            ll x=i,y=j;
            if(a[x]<a[y]) swap(x,y);
            if(a[y]==0) continue;
            if(a[x]%a[y]==0) {
                if(dsr[x].count(a[x]/a[y])) {
                   Add(x,y+n,0x3f3f3f3f3f3fLL,c[x]*c[y]);
                   Add(y,x+n,0x3f3f3f3f3f3fLL,c[x]*c[y]);                   
                }
            }
        }
    }
    printf("%lld\n",EK()/2LL);
    return 0;
}