[SDOI2016]数字配对（费用流+贪心+trick）

重点是如何找到可以配对的\(a[i]\)和\(a[j]\)。

把\(a[i]\)分解质因数。设\(a[i]\)分解出的质因数的数量为\(cnt[i]\)。

设\(a[i]\geq a[j]\)

那么\(a[i]\)可以和\(a[j]\)配对需要满足\(a[i]\)%\(a[j]==0\)&&\(cnt[i]==cnt[j]+1\)

证明显然。

然后我们按\(cnt[i]\)的奇偶分成两部分，然后如果\(a[i]\)和\(a[j]\)可以配对（假设a[i]在左边）从\(i\)向\(j\)连一条费用为\(c[i]*c[j\)]，流量为\(INF\)的边。

然后\(S\)向左部点连费用为\(0\)，流量为\(b[i]\)的边。

然后每一个右部点向\(T\)连费用为\(0\)，流量为\(b[i]\)的边。

跑费用流。

因为费用流优先走最长路。

所以我们可以贪心。

当总费用刚好为负时结束就好了。

具体来说这次增广前的总费用为\(tot\)，总流量为\(w\)。

然后这次最长路长度为\(x\)，可以增广的流量为\(tmp\)。

且\(tot+x*tmp<0\)，答案就是\(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];

	ans+=mn;

	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;

}

巴特西

[SDOI2016]数字配对（费用流+贪心+trick）

最新文章

热门文章