数字配对(最小费用最大流)

题目链接:https://cn.vjudge.net/contest/281959#problem/C

解题思路:建图由百度易得,当两个数的素因子个数都是奇数/都是偶数时,两数相除一定不是一个质数,那么,有可能可以相连的就一定是素因子个数不同的了。因此,我们把素因子奇数个的放在左边,偶数个的放在右边,就像二分图那样,然后再把左边的都与源点相连,右面的都与汇点相连,之间的暴力判断一下是否满足题意再相连,建图就完事了。

但是,本题是个假的最小费用最大流,实际上它是一个最大费用最大流,因为你要尽可能的防止你的总权值是负数。所以,要把模板的spfa改一改,大于号改成小于号。

cnt忘记初始化0调了一下午,,,被自己蠢哭。。。

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node
{
    long long next,len,w,to;
} edge[100000];

long long head[5050],cnt,flow[100010],vis[100010],pre[100010],last[100010];
long long maxflow,mincost;
long long dis[100010];

void addedge(long long u,long long v,long long len,long long w)
{
    edge[cnt].to=v;
    edge[cnt].len=len;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

bool spfa(long long s,long long t)
{
    memset(dis,-0x7f,sizeof(dis));
    memset(flow,0x7f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    deque<int>q;
    q.push_back(s);
    vis[s]=1;
    dis[s]=0;

    flow[s]=0x3f3f3f3f;

    pre[t]=-1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop_front();
        vis[now]=0;
        for(int i=head[now]; i!=-1; i=edge[i].next)
        {
            if(edge[i].len>0&&dis[edge[i].to]<dis[now]+edge[i].w)
            {
                dis[edge[i].to]=dis[now]+edge[i].w;
                pre[edge[i].to]=now;
                last[edge[i].to]=i;
                flow[edge[i].to]=min(flow[now],edge[i].len);
                if(!vis[edge[i].to])
                {
                    vis[edge[i].to]=1;
                    q.push_back(edge[i].to);
                }
            }
        }
    }
    return pre[t]!=-1;
}

void mcmf(int s,int t)
{
    while(spfa(s,t))
    {
        if(mincost+dis[t]*flow[t]<0ll)
        {
            maxflow+=mincost/(-dis[t]);
            break;
        }
        int now=t;
        maxflow+=flow[t];
        mincost+=flow[t]*dis[t];
        while(now!=s)
        {
            edge[last[now]].len-=flow[t];
            edge[last[now]^1].len+=flow[t];
            now=pre[now];
        }
    }
}

long long a[220],b[220],c[220],odd[220];

bool prime(int x)
{
    for(int i = 2; i * i <= x; i++)
        if(x % i == 0)
            return false;
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;

    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    for(int i=1; i<=n; i++)
    {
        cin>>b[i];
    }
    for(int i=1; i<=n; i++)
    {
        cin>>c[i];
    }

    for(int i=1; i<=n; i++)
    {
        int d=a[i],ccnt=0;
        for(int j=2; j*j<=d; j++)
        {
            while(d%j==0)
            {
                d/=j;
                ccnt++;
            }
        }
        if(d!=1)
            ccnt++;
        if(ccnt&1)
            odd[i]=1;
        else
            odd[i]=0;
    }

    memset(head,-1,sizeof(head));
    cnt=0;
    for(int i=1; i<=n; i++)
    {
        if(odd[i])
        {
            addedge(0,i,b[i],0LL);
            addedge(i,0,0,0LL);
        }
        else
        {
            addedge(i,n+1,b[i],0LL);
            addedge(n+1,i,0,0ll);
        }
    }

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(odd[i]&&!odd[j])
            {
                int tx,ty;
                tx=a[i];
                ty=a[j];
                if(tx<ty)
                {
                    swap(tx,ty);
                }
                if(tx%ty==0&&prime(tx/ty))
                {
                    addedge(i,j,0x3f3f3f3f,1ll*c[i]*c[j]);
                    addedge(j,i,0,-1ll*c[i]*c[j]);
                }
            }
        }
    }

    mcmf(0,n+1);
    cout<<maxflow<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注