C – 数字配对 (费用流)

  • 2019-02-03
  • 0
  • 0

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

题意:中文题就不解释了

思路:当两个数的素因子个数都是奇数或者都是偶数时,两数相除一定不是一个质数,所以把奇数的放在一边,偶数的放在一边,可以匹配的建边,左边的与源点相连,右边的有汇点相连。
题目要求价值>0,所以spfa求最长路,按照最长路的路径进行增广

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int inf=0x3f3f3f3f;
struct node
{
    ll to,w,len,next;
}e[100005];
ll head[5050],cnt;
ll flow[100010],vis[100010],pre[100010],last[100010];
ll maxflow,mincost;
ll dis[100010];
ll a[220],b[220],c[220],odd[220];

void add(ll u,ll v,ll len,ll w)
{
    e[cnt]=node{v,w,len,head[u]};
    head[u]=cnt++;
}

bool spfa(ll s,ll t)
{
    memset(dis,-0x7f,sizeof(dis));
    memset(flow,0x7f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    deque<ll>q;
    q.push_back(s);
    vis[s]=1;
    dis[s]=0;
    flow[s]=inf;
    pre[t]=-1;
    while(!q.empty())
    {
        ll x=q.front();
        q.pop_front();
        vis[x]=0;
        for(ll i=head[x];i!=-1;i=e[i].next)
        {
            ll to=e[i].to;
            ll len=e[i].len;
            ll w=e[i].w;
            if(len>0&&dis[to]<dis[x]+w)
            {
                dis[to]=dis[x]+w;
                pre[to]=x;
                last[to]=i;
                flow[to]=min(flow[x],len);
                if(!vis[to])
                {
                    vis[to]=1;
                    q.push_back(to);
                    ll aaa=q.front(),bbb=q.back();
                    if(dis[aaa]<dis[bbb])
                    {
                        q.pop_back();
                        q.pop_front();
                        q.push_back(aaa);
                        q.push_front(bbb);
                    }
                }
            }
        }
    }
    return pre[t]!=-1;
}

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

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

int main()
{
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    for(ll i=1;i<=n;i++)
    {
        cin>>c[i];
    }

    for(ll i=1;i<=n;i++)
    {
        int d=a[i],num=0;
        for(int j=2;j*j<=d;j++)
        {
            while(d%j==0)
            {
                num++;
                d/=j;
            }
        }
        if(d!=1)num++;
        if(num&1)odd[i]=1;
        else odd[i]=0;
    }
    memset(head,-1,sizeof(head));
    cnt=0;
    for(ll i=1;i<=n;i++)
    {
        if(odd[i])
        {
            add(0,i,b[i],0LL);
            add(i,0,0,0LL);
        }
        else
        {
            add(i,n+1,b[i],0LL);
            add(n+1,i,0,0LL);
        }

    }

    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=n;j++)
        {
            if(odd[i]&&!odd[j])
            {
                ll x,y;
                x=a[i];
                y=a[j];
                if(x<y)
                {
                    swap(x,y);
                }
                if(x%y==0&&prime(x/y))
                {
                    add(i,j,inf,1LL*c[i]*c[j]);
                    add(j,i,0,-1LL*c[i]*c[j]);
                }
            }
        }
    }
    mcmf(0,n+1);
    cout<<maxflow<<endl;
    return 0;
}

评论

还没有任何评论,你来说两句吧