[SDOI2016] Digital pairing (cost flow + greedy + trick)

The point is how to find a match$a[i]$and$a[j]$.
Bundle$a[i]$Decompose prime factors. Assume$a[i]$The number of prime factors decomposed is$cnt[i]$.
Assume$a[i]\geq a[j]$
So$a[i]$can and$a[j]$Pairing needs to be satisfied$a[i]$%$a[j]==0$&&$cnt[i]==cnt[j]+1$
The proof is obvious.
Then we press$cnt[i]$The parity is divided into two parts, then if$a[i]$and$a[j]$can be paired (assuming a[i] is on the left) from$i$Towards$j$A fee for$c[i]c[j$], the flow is$INF$edge.
Then$S$Connect to the left for a fee of$0$, the flow is$b[i]$edge.
Then each right point$T$The cost is$0$, the flow is$b[i]$edge.
Running cost flow.
Because the cost flow takes the longest path first.
So we can be greedy.
It’s good to end when the total cost is just negative.
Specifically, the total cost before this augmentation is$tot$, the total flow is$w$.
Then the longest path length this time is$x$, the flow that can be increased is$tmp$.
and$tot+x
tmp<0$, the answer is$w+\lfloor \frac{tot}{x} \rfloor$

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long
const int N=233;
const int INF=1e14;
int read(){
    int sum=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return sum*f;
}
int book[101000],prime[100100],tot;
void pre_work(int n){
    for(int i=2;i<=n;i++){
        if(book[i]==0)prime[++tot]=i;
        for(int j=1;j<=tot&&prime[j]*i<=n;j++){
            book[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int work(int x){
    int tmp=0;
    for(int i=1;prime[i]*prime[i]<=x;i++)
        if(x%prime[i]==0){
            while(x%prime[i]==0)x/=prime[i],tmp++;
        }
    if(x>1)tmp++;
    return tmp;
}
struct edge{
    int to,nxt,flow,cost;
}e[N*N*2];
int cnt=1,head[N];
void add_edge(int u,int v,int flow,int cost){
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].flow=flow;
    e[cnt].cost=cost;
    head[u]=cnt;
    cnt++;
    e[cnt].nxt=head[v];
    e[cnt].to=u;
    e[cnt].flow=0;
    e[cnt].cost=-cost;
    head[v]=cnt;
}
int dis[N],vis[N],road[N],S,T,tmp,ans;
bool spfa(){
    for(int i=S;i<=T;i++)dis[i]=INF;
    queue<int> q;
    q.push(S);
    dis[S]=0;
    vis[S]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].flow&&dis[v]>dis[u]+e[i].cost){
                dis[v]=dis[u]+e[i].cost;
                road[v]=i;
                if(vis[v]==0){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dis[T]==INF)return false;
    int mn=INF;
    for(int i=T;i!=S;i=e[road[i]^1].to)
        mn=min(e[road[i]].flow,mn);
    if(tmp+mn*dis[T]>0){
        ans+=-tmp/dis[T];
        return  false ;
    }
    tmp+=mn*dis[T];
    years+=min;
    for(int i=T;i!=S;i=e[road[i]^1].to){
        e[road[i]].flow-=mn;
        e[road[i]^1].flow+=mn;
    }
    return true;
}
int n,a[N],b[N],c[N],w[N];
signed main(){
    pre_work(100000);
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();
    for(int i=1;i<=n;i++)c[i]=read();
    for(int i=1;i<=n;i++)w[i]=work(a[i]);
    S=0;T=n+1;
    for(int i=1;i<=n;i++)
        if(w[i]%2==1)add_edge(S,i,b[i],0);
        else add_edge(i,T,b[i],0);
    for(int i=1;i<=n;i++){
        if(w[i]%2==0)continue;
        for(int j=1;j<=n;j++){
            if(w[j]%2==1)continue;
            if((a[j]%a[i]==0&&w[j]==w[i]+1)||(a[i]%a[j]==0&&w[i]==w[j]+1))
                add_edge(i,j,INF,-c[i]*c[j]);
        }
    }
    while(spfa());
    printf("%lld",ans);
    return 0;
}

Reprinted in: /Xu-daxia/p/10513573.html

Leave a Comment

Your email address will not be published. Required fields are marked *