[SDOI2016]数字配对

C++14(g++5.4) 解法, 执行用时: 36ms, 内存消耗: 3308K, 提交时间: 2020-06-25 09:29:26

#include<bits/stdc++.h>  // 最大费用最大流
#define inf 0x7f7f7f7f
#define linf (1ll<<61)
#define ll long long
using namespace std;
const int MX=1e5+9;
int pre[MX],tot=0;
void init(){
    int vis[MX];
    for( int i=2 ; i<=100000 ; i++ ){
        if( !vis[i] )
            pre[++tot]=i;
        for( int j=1 ; pre[j]<=100000/i ; j++ ){
            int k=i*pre[j];
            vis[k]=1;
            if( (i%pre[j])==0 )
                break;
        }
    }
}
int get(int a){
    int ans=0,c=1;
    for( int i=1 ; i<=tot ; i++ ){
        while( a%pre[i]==0 ){
            a/=pre[i];
            ans++;
        }
    }
    if( a>1 )
        return ans+1;
    else
        return ans;
}

int n,A[MX],a[MX],S,T;
ll val[MX];
struct node{
    int u,v,c,next;
    ll val;
}t[1000009];
int head[MX],cnt=-1;
void add(int u,int v,int c,ll val){
    t[++cnt].next=head[u],head[u]=cnt;
    t[cnt].u=u,t[cnt].v=v,t[cnt].c=c,t[cnt].val=val;
    t[++cnt].next=head[v],head[v]=cnt;
    t[cnt].u=v,t[cnt].v=u,t[cnt].c=0,t[cnt].val=-val;
}

int vis[MX],frm[MX],minc[MX];
ll dis[MX];
int spfa(){
    for( int i=0 ; i<MX ; i++ )
        dis[i]=-linf;
    memset(frm,-1,sizeof(frm));
    memset(vis,0,sizeof(vis));
    memset(minc,inf,sizeof(minc));
    queue<int> que;
    que.push(S);
    dis[S]=0;
    while( !que.empty() ){
        int u=que.front();
        que.pop();
        vis[u]=0;
        for( int num=head[u] ; ~num ; num=t[num].next ){
            int v=t[num].v,c=t[num].c;
            ll val=t[num].val;
            if( c && dis[v]<dis[u]+val ){
                dis[v]=dis[u]+val;
                frm[v]=num;
                minc[v]=min(minc[u],c);
                if( !vis[v] ){
                    vis[v]=1;
                    que.push(v);
                }
            }
        }
    }
    if( dis[T]>-linf )
        return 1;
    return 0;
}

int ans=0;
ll mxcost;
void dinic(){
    while( spfa() ){
        if( mxcost+1ll*minc[T]*dis[T]<0 ){
            ans+=(mxcost/(-dis[T]));
            break;
        }
        ans+=minc[T];
        mxcost+=1ll*minc[T]*dis[T];
        for( int num=frm[T] ; ~num ; num=frm[t[num].u] ){
            t[num].c-=minc[T];
            t[num^1].c+=minc[T];
        }
    }
}

int main()
{
//    freopen("input.txt","r",stdin);
    memset(head,-1,sizeof(head));
    init();
    scanf("%d",&n);
    for( int i=1 ; i<=n ; i++ ){
        scanf("%d",&A[i]);
        a[i]=get(A[i]);
    }
    S=n+1,T=n+2;
    for( int i=1,c ; i<=n ; i++ ){
        scanf("%d",&c);
        (a[i]%2)?add(S,i,c,0):add(i,T,c,0);
    }
    for( int i=1 ; i<=n ; i++ )
        scanf("%lld",&val[i]);
    for( int i=1 ; i<=n ; i++ ){
        if( a[i]%2 ){
            for( int j=1 ; j<=n ; j++ )
                if( abs(a[i]-a[j])==1 && (A[i]%A[j]==0 || A[j]%A[i]==0) )  // 可能i和j虽然是关于1的差关系，但不是倍数关系，比如4（2）和27（3）
                    add(i,j,inf,val[i]*val[j]);
        }
    }
    dinic();
    printf("%d\n",ans);
    return 0;
}

C++(clang++11) 解法, 执行用时: 4ms, 内存消耗: 408K, 提交时间: 2021-08-14 13:44:53

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
using namespace std;
const int N=211; typedef long long lll;
const lll inf=1e15; queue<int>q; lll dis[N],ans;
struct node{int y; lll w,f; int next;}e[N<<3];
int as[N],v[N],dep[N],n,m,S,T,a[N],b[N],et=1,c[N];
inline signed iut(){
	int ans=0,f=1; char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans*f;
}
inline void add(int x,int y,lll w,lll f){
	e[++et]=(node){y,w,f,as[x]},as[x]=et;
	e[++et]=(node){x,0,-f,as[y]},as[y]=et;
}
inline bool spfa(){
	for (int i=1;i<=T;++i) dis[i]=inf,v[i]=0,dep[i]=0;
	dis[T]=0,v[T]=1,q.push(T);
	while (!q.empty()){
		int x=q.front(); q.pop();
		for (int i=as[x];i;i=e[i].next)
		if (e[i^1].w&&dis[e[i].y]>dis[x]-e[i].f){
			dis[e[i].y]=dis[x]-e[i].f,dep[e[i].y]=dep[x]+1;
			if (!v[e[i].y]) v[e[i].y]=1,q.push(e[i].y);
		}
		v[x]=0;
	}
	return dis[S]<inf;
}
inline lll dfs(int x,lll now){
	if (x==T) {v[T]=1; return now;}
	lll rest=0,f; v[x]=1;
	for (int i=as[x];i;i=e[i].next)
	if (!v[e[i].y]&&e[i].w&&dep[e[i].y]==dep[x]-1&&dis[e[i].y]+e[i].f==dis[x]){
		rest+=(f=dfs(e[i].y,min(e[i].w,now-rest)));
		if (f) e[i].w-=f,e[i^1].w+=f;
		if (rest==now) break;
	}
	return rest;
}
inline signed answ(int x){
	int ans=0;
	for (int i=2;i*i<=x;++i)
	    while (x%i==0) x/=i,++ans;
	if (x>1) ++ans;
	return ans;
}
signed main(){
	n=iut(),S=n+1,T=S+1;
	for (int i=1;i<=n;++i) c[i]=answ(a[i]=iut());
	for (int i=1;i<=n;++i)
	if (c[i]&1) add(i,T,iut(),0);
	    else add(S,i,iut(),0);
	for (int i=1;i<=n;++i) b[i]=iut();
	for (int i=1;i<=n;++i) if (c[i]&1)
	for (int j=1;j<=n;++j)
	if ((c[j]+1==c[i]&&a[i]%a[j]==0)||(c[j]-1==c[i]&&a[j]%a[i]==0))
	    add(j,i,inf,-1ll*b[i]*b[j]);
	for (lll now,sum=0;spfa();){
		v[T]=1,now=0;
		while (v[T]){
			memset(v,0,sizeof(v));
			now+=dfs(S,inf);
		}
		if (sum>=now*dis[S]) sum-=now*dis[S],ans+=now;
		    else {ans+=sum/dis[S]; break;}
	}
	return !printf("%lld",ans);
}

详情