Cogs 2221. [SDOI2016 Round1] 数字配对(二分图)

[SDOI2016 Round1] 数字配对

★★★ 输入文件：menci_pair.in 输出文件：menci_pair.out 简单对比

时间限制：1 s 内存限制：128 MB

【题目描述】

有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。

若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数，那么这两个数字可以配对，并获得 ci×cj 的价值。

一个数字只能参与一次配对，可以不参与配对。

在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。

【输入格式】

第一行一个整数 n。

第二行 n 个整数 a1、a2、……、an。

第三行 n 个整数 b1、b2、……、bn。

第四行 n 个整数 c1、c2、……、cn。

【输出格式】

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

【样例输入】

3

2 4 8

2 200 7

-1 -2 1

【样例输出】

4

【提示】

测试点 1 ~ 3：n≤10，ai≤109，bi=1，∣ci∣≤105；

测试点 4 ~ 5：n≤200，ai≤109，bi≤105，ci=0；

测试点 6 ~ 10：n≤200，ai≤109，bi≤105，∣ci∣≤105。

【来源】

SDOI2016 Round1 Day1

/*

二分图匹配.

建图挺妙的.

把一个数拆开.

若两个数字ai,aj满足,ai是aj的倍数,且ai/aj是一个质数.

这个东西的充要条件是

①两个数是倍数关系

②两个数质因数分解后指数和相差为1.

也就是说两个数要想配对,那么他必须满足②这个必要条件.

so 我们可以根据这个建图.

根据分解后质数的和的奇偶性分为两类.

我们贪心的跑一个最大费用,所以费用是不严格单调的.

当当前的一个总费用>=0时我们继续增广.

否则我们就把下界的值加上.

关于下界的处理:

费用>=0且最后一次增广时(排除找不到增广路的情况),

我们发现dis[T]是<0的,我们虽然不能跑x*dis[T]的费用,

但是我们可能能跑sum/-dis[T](下取整)的费用.

(我们也可以把费用取反,然后贪心的跑最小费用.

然后就变成了一个简单的最小(or 最大)费用流最大流问题.

要注意longlong 还有下界的一些东西.

*/

#include<iostream>

#include<cstdio>

#include<cmath>

#include<queue>

#define INF 1e18

#define MAXN 40010

#define LL long long

using namespace std;

int n,m,head[MAXN],a[MAXN],max1,cut=1,tot,S,T,b[MAXN],pre[MAXN];

LL dis[MAXN],ans,sum;

bool pri[MAXN];

queue<int>q;

struct data{int a,b;LL c;}s[MAXN];

struct edge{int u,v,next;LL c,f;}e[MAXN*2];

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void add(int u,int v,LL c,LL f)

{

    e[++cut].u=u,e[cut].v=v,e[cut].c=c,e[cut].f=f,e[cut].next=head[u],head[u]=cut;

    e[++cut].u=v,e[cut].v=u,e[cut].c=0,e[cut].f=-f,e[cut].next=head[v],head[v]=cut;

}

void slovepri()

{

    for(int i=2;i<=sqrt(max1)+1;i++)

    {

        if(!pri[i])

        {

            a[++tot]=i;

            for(int j=i+i;j<=sqrt(max1);j+=i) pri[j]=true;//sb w.

        }

    }

    return ;

}

bool judge(int x)

{

    for(int i=2;i<=sqrt(x);i++) if(x%i==0) return false;

    return true;

}

int check(int x)

{

    int total=0;

    for(int i=1;i<=tot;i++)

    {

        while(x%a[i]==0) x/=a[i],total++;

        if(x==1) return total;

    }

    return total;

}

void slove()

{

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

    {

        int x=check(s[i].a);

        if(x&1) add(S,i,s[i].b,0);

        else add(i,T,s[i].b,0);

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

        {

            if(j==i) continue;

            if(s[i].a%s[j].a==0&&judge(s[i].a/s[j].a))

            {

                if(x&1) add(i,j,INF,s[i].c*s[j].c);

                else add(j,i,INF,s[i].c*s[j].c);

            }

        }

    }

    return ;

}

bool bfs(int t)

{

    for(int i=S;i<=T;i++) dis[i]=-INF;

    q.push(S);dis[S]=0;b[S]=T;

    while(!q.empty())

    {

        int u=q.front();q.pop();b[u]=0;

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].v;

            if(dis[v]<dis[u]+e[i].f&&e[i].c)

            {

                dis[v]=dis[u]+e[i].f;pre[v]=i;

                if(b[v]!=t) b[v]=t,q.push(v);

            }

        }

    }

    return dis[T]!=-INF;

}

void dinic()

{

    int t=1;

    while(bfs(t))

    {

        int tmp=pre[T];LL x=INF;

        while(tmp) x=min(x,e[tmp].c),tmp=pre[e[tmp].u];

        tmp=pre[T];

        while(tmp)

        {

            e[tmp].c-=x;

            e[tmp^1].c+=x;

            tmp=pre[e[tmp].u];

        }

        if(sum+x*dis[T]>=0)

        {

            sum+=x*dis[T];ans+=x;

        }

        else {ans+=(sum/-dis[T]);return ;}

        t++;

    }

    return ;

}

int main()

{

    freopen("menci_pair.in","r",stdin);

    freopen("menci_pair.out","w",stdout);

    n=read();S=0,T=n+1;

    for(int i=1;i<=n;i++) s[i].a=read(),max1=max(max1,s[i].a);

    for(int i=1;i<=n;i++) s[i].b=read();

    for(int i=1;i<=n;i++) s[i].c=read();

    slovepri();slove();dinic();

    printf("%d",ans);

    return 0;

}

巴特西

Cogs 2221. [SDOI2016 Round1] 数字配对(二分图)

最新文章

热门文章