bzoj-4514(网络流)-布布扣-bubuko.com

题目链接：

4514: [Sdoi2016]数字配对

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

思路：

这是一个有限制条件的最大匹配问题,可以把每个点拆成左右两个点,左边与源点相连,右边与汇点相连,容量为b[i],费用为零,左右的一对点若满足题目要求的关系,

那么就连一对容量为无穷,费用为c[i]*c[j]的边,这两条边对称,最后建出来的图也是对称的,所以ans/2，在跑费用流的时候要用spfa沿最长路增广,判断费用和0的大小,就可以得到答案了;

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=210;
const LL inf=1e18;
int n;
LL A[maxn],B[maxn],C[maxn];
struct Edge
{
    int from,to;
    LL cap,flow,cost;
};
int m,s,t,inq[2*maxn],p[2*maxn];
LL d[2*maxn],a[2*maxn];
std::vector<Edge> edge;
std::vector<int> G[2*maxn];
inline void add_edge(int from,int to,LL cap,LL cost)
{
    edge.push_back((Edge){from,to,cap,0,cost});
    edge.push_back((Edge){to,from,0,0,-cost});
    m=edge.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
}
bool bellmanford(LL &flow,LL &cost)
{
    for(int i=s;i<=t;i++)d[i]=-inf;
    memset(inq,0,sizeof(inq));
    d[s]=0;inq[s]=1;p[s]=0;a[s]=inf;
    queue<int>qu;
    qu.push(s);
    while(!qu.empty())
    {
        int fr=qu.front();qu.pop();inq[fr]=0;
        int len=G[fr].size();
        for(int i=0;i<len;i++)
        {
            Edge& e=edge[G[fr][i]];
            if(e.cap>e.flow&&d[e.to]<d[fr]+e.cost)
            {
                d[e.to]=d[fr]+e.cost;
                p[e.to]=G[fr][i];
                a[e.to]=min(a[fr],e.cap-e.flow);
                if(!inq[e.to]){qu.push(e.to);inq[e.to]=1;}
            }
        }
    }
    if(d[t]<=-inf)return false;
    if(cost+d[t]*a[t]<0)
    {
        LL tep=cost/(-d[t]);
        flow+=tep;
        return false;
    }
    flow+=a[t];
    cost+=d[t]*a[t];
    int u=t;
    while(u!=s)
    {
        edge[p[u]].flow+=a[t];
        edge[p[u]^1].flow-=a[t];
        u=edge[p[u]].from;
    }
    return true;
}
inline LL mincostflow()
{
    LL flow=0;
    LL cost=0;
    while(bellmanford(flow,cost));
    return flow;
}
inline LL pow_mod(LL x,LL y,LL mod)
{
    LL s=1,base=x;
    while(y)
    {
        if(y&1)s=s*base%mod;
        base=base*base%mod;
        y>>=1;
    }
    return s;
}
inline int isprime(LL num)
{
    if(num<=1)return 0;
    if(num==2)return 1;
    if(num%2==0)return 0;
    for(int i=1;i<=50;i++)
    {
        LL x=rand()%num;
        if(x==0)x++;
        if(pow_mod(x,num-1,num)!=1)return 0; 
    }
    return 1;
}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&A[i]);
    for(int i=1;i<=n;i++)scanf("%lld",&B[i]);
    for(int i=1;i<=n;i++)scanf("%lld",&C[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(A[i]/A[j]<=1||A[i]%A[j])continue;
            if(isprime(A[i]/A[j]))
            {
                add_edge(j,i+n,100000000,(LL)C[i]*C[j]);
                add_edge(i,j+n,100000000,(LL)C[i]*C[j]);
            }
        }
    }
    s=0,t=2*n+1;
    for(int i=1;i<=n;i++)add_edge(s,i,B[i],0),add_edge(n+i,t,B[i],0);
    printf("%lld\n",mincostflow()/2);
    return 0;
}

bzoj-4514(网络流)

原文：http://www.cnblogs.com/zhangchengc919/p/6136045.html