(BZOJ) 4514: [Sdoi2016]数字配对

http://www.lydsy.com/JudgeOnline/problem.php?id=4514

先把數字分成兩類：質因數各數有奇數個的或有偶數個的

這樣一來，圖就是二分圖了。

之後再用min cost max flow亂搞即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;

#define SZ(x) ((int)(x).size())

struct Kirino
{
    static const int N = 206;
    struct Edge
    {
        LL to,cap,rev,cost;
        Edge(LL _to,LL _cap,LL _rev,LL _cost)
        {
            to = _to;
            cap = _cap;
            rev = _rev;
            cost = _cost;
        }
    };
    vector<Edge> G[N];
    void add_edge(int from,int to,LL cap,LL cost)
    {
        G[from].push_back(Edge(to,cap,SZ(G[to]),cost));
        G[to].push_back(Edge(from,0,SZ(G[from])-1,-cost));
    }
    int n,s,t;
    void init(int _n,int _s,int _t)
    {
        n=_n;
        s=_s;
        t=_t;
        for (int i=0;n>=i;i++)
        {
            G[i].clear();
        }
    }
    LL dis[N];
    int pre[N],pre_id[N];
    bool in_que[N];
    pii sagiri()
    {
        LL flow=0,cost=0;
        LL INF = (1LL<<40);
        while (true)
        {
            memset(in_que,0,sizeof(in_que));
            fill(dis,dis+n+1,INF);
            queue<int> que;
            que.push(s);
            dis[s]=0;
            while (!que.empty())
            {
                int t=que.front();
                que.pop();
                in_que[t] = false;
                for (int i=0;SZ(G[t])>i;i++)
                {
                    Edge e=G[t][i];
                    if (e.cap > 0 && dis[e.to] > dis[t] + e.cost)
                    {
                        dis[e.to] = dis[t] + e.cost;
                        pre[e.to] = t;
                        pre_id[e.to] = i;
                        if (!in_que[e.to])
                        {
                            in_que[e.to] = 1;
                            que.push(e.to);
                        }
                    }
                }
            }
            if (dis[t] == INF) break;
            LL mn_flow = INF;
            for (int i=t;i!=s;i=pre[i])
            {
                mn_flow = min( mn_flow, G[ pre[i] ][ pre_id[i] ].cap  );
            }
            if (mn_flow*dis[t]+cost > 0)
            {
                int L=0,R=mn_flow; //L is the answer
                while (R-L != 1)
                {
                    int mid=(L+R)>>1;
                    if (mid*dis[t] + cost > 0) R=mid;
                    else L=mid;
                }
                flow += L;
                cost += L*dis[t];
                break;
            }
            flow += mn_flow;
            cost += mn_flow*dis[t];
            for (int i=t;i!=s;i=pre[i])
            {
                G[ pre[i] ][ pre_id[i] ].cap -= mn_flow;
                G[ i ][ G[ pre[i] ][ pre_id[i] ].rev ].cap += mn_flow;
            }
        }
        return make_pair(flow,cost);
    }
} meruru;

const int N = 206;

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

vector<int> v[N];

vector<int> get_p(LL x)
{
    vector<int> ret;
    for (int i=2;i*i<=x;i++)
    {
        while (x%i==0)
        {
            ret.push_back(i);
            x/=i;
        }
    }
    if (x != 1) ret.push_back(x);
    return ret;
}

int main()
{
    int n;
    scanf("%d",&n);
    int INF = 1000000007;
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]);
        v[i] = get_p(a[i]);
    }
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&b[i]);
    }
    for (int i=1;n>=i;i++)
    {
        scanf("%lld",&c[i]);
    }
    int s=0,t=n+1;
    meruru.init(t,s,t);
    for (int i=1;n>=i;i++)
    {
        if (SZ(v[i])%2==1)
        {
            meruru.add_edge(s,i,b[i],0);
        }
        else
        {
            meruru.add_edge(i,t,b[i],0);
        }
        for (int j=1;n>=j;j++)
        {
            if (i==j) continue;
            if (a[i]%a[j] == 0 && SZ(v[i]) - SZ(v[j]) == 1)
            {
                int ii=i,jj=j;
                if (SZ(v[ii])%2 == 0) swap(ii,jj);
                meruru.add_edge(ii,jj,INF,-c[ii]*1LL*c[jj]);
            }
        }
    }
    pii ret=meruru.sagiri();
    printf("%lld\n",ret.first);
}