SDOI 2016 数字配对

时间：2021-12-03 07:44:35

题目大意：给定n个数字以及每个数字的个数和权值，将满足条件的数字配对，使得总代价不小于0，且配对最多

最大费用最大流拆点，对于每个点，连一条由S到该点的边，容量为b，花费为0，再连一条到T的边

对于每个合法的配对，连一条容量无穷，费用为ci*cj的边

跑最大费用最大流即可

#include<bits/stdc++.h>

using namespace std;

#define inf (1ll<<50)

#define ll long long

struct edge{

    int to,next,flom;

    ll cost,cap;

}G[];

int tot=,h[];

int S,T,ans;

ll cost;

int n;

int a[],b[],c[];

void add(int x,int y,ll z,ll c){

    tot++;G[tot].to=y;G[tot].next=h[x];h[x]=tot;G[tot].flom=x;G[tot].cap=z;G[tot].cost=c;

}

void ins(int x,int y,ll z,ll c){

    add(x,y,z,c);add(y,x,,-c);

}

ll dis[];int vis[],p[];

bool check(int x){

    int k=sqrt(x);

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

        if(x%i==)return ;

    return ;

}

bool spfa(){

    memset(vis,,sizeof(vis));

    memset(p,,sizeof(p));

    for(int i=;i<=(n<<|);++i)dis[i]=-inf;dis[S]=;

    queue<int>Q;Q.push(S);vis[S]=;

    while(!Q.empty()){

        int u=Q.front();Q.pop();vis[u]=;

        for(int i=h[u];i;i=G[i].next){

            int v=G[i].to;

            if(G[i].cap>&&dis[v]<dis[u]+G[i].cost){

                dis[v]=dis[u]+G[i].cost;p[v]=i;

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

            }

        }

    }

    return dis[T]>-inf;

}

void mcf(){

    int t=T;ll k=inf;

    while(t){

        t=p[t];k=min(k,G[t].cap);t=G[t].flom;

    }

    t=T;ll c=;

    while(t){

        t=p[t];c+=G[t].cost;G[t].cap-=k;G[t^].cap+=k;t=G[t].flom;

    }

    if(cost+c*k>=){

        ans+=k;cost+=c*k;

    }else{

        k=cost/(-c);

        ans+=k;

        printf("%d\n",ans/);

        exit();

    }

}

int main(){

    scanf("%d",&n);S=,T=;

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

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

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

    for(int i=;i<=n;++i)ins(S,i<<,b[i],);

    for(int i=;i<=n;++i)ins(i<<|,T,b[i],);

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

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

            if((a[i]%a[j]==||a[j]%a[i]==)&&a[i]!=a[j]){

                int k=a[i]>a[j]?a[i]/a[j]:a[j]/a[i];

                if(check(k))ins(i<<,j<<|,inf,1ll*c[i]*c[j]),ins(j<<,i<<|,inf,1ll*c[i]*c[j]);

            }

    while(spfa())mcf();

    printf("%d\n",ans/);

}

相关文章