文章目錄

• 題目描述
• 解析
• 代碼

題目描述

有n種數字，第 i 種數字是 ai，有 bi個，權值是 ci。

若兩個數字 ai,aj 滿足， ai 是 aj 的倍數，且 ai/aj 是一個質數，那么這兩個數字可以配對，并獲得 ci*cj 的價值。

一個數字只能參與一次配對，可以不參與配對。

在獲得的價值總和不小于 0 的前提下，求最多進行多少次配對。

解析

很神奇的題
考慮限制條件的轉化
把每個數字進行質因數分解，設 ai 的質因子個數為 cnti
那么ai、aj可以配對的充要條件為

1.ai | aj
2.cnti=cntj-1

注意到，兩個數字能夠配對，當且僅當它們cnt的奇偶性不同
所以如果我們按照cnt的奇偶性分類的話，這就成了一個二分圖
然后問題就簡單了，變成了一個配對問題
注意題目要求價值不小于0的條件下的最大流，又因為dinic本身就是貪心的算法，所以我們直接讓它跑到價值用盡即可

代碼

#include<bits/stdc++.h> using namespace std; const int N=1e5+100; const int M=2e6+100; #define ll long long ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();};return x*f; } int n,m,s,t; struct node{int to,nxt;ll cap,w; }p[M<<1]; int fi[N],cur[N],cnt=-1; void addline(int x,int y,ll cap,ll w){p[++cnt]=(node){y,fi[x],cap,w};fi[x]=cnt;p[++cnt]=(node){x,fi[y],0,-w};fi[y]=cnt; } ll flow,cost; queue<int>q; bool vis[N]; ll dis[N]; bool jd; bool spfa(){if(jd) return false;bool flag=0;memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));dis[s]=0;q.push(s);while(!q.empty()){int now=q.front();q.pop();vis[now]=0;for(int i=cur[now]=fi[now];~i;i=p[i].nxt){int to=p[i].to;if(!p[i].cap) continue;if(dis[to]>dis[now]+p[i].w){dis[to]=dis[now]+p[i].w;if(to==t) flag=1;if(!vis[to]){q.push(to);vis[to]=1;}}}}return flag; } ll dfs(int x,ll lim){if(jd) return 0;if(x==t||!lim){//printf("lim=%lld dis=%lld\n",lim,dis[t]);if(cost+lim*dis[t]>0){jd=1;ll add=(-cost)/dis[t];return add;}cost+=lim*dis[t];return lim;}ll res=0;vis[x]=1;for(int &i=cur[x];~i;i=p[i].nxt){int to=p[i].to;if(vis[to]||!p[i].cap||dis[to]!=dis[x]+p[i].w) continue;ll add=dfs(to,min(lim,p[i].cap));res+=add;lim-=add;p[i].cap-=add;p[i^1].cap+=add;if(!lim) break;}vis[x]=0;if(lim) dis[x]=-1;return res; } void dinic(){flow=cost=0;while(spfa()){while(ll tmp=dfs(s,2e18)) flow+=tmp;} } int ccnt[N],prime[N],tp,num,v[N]; void find_prime(){int tp=100000;for(int i=2;i<=tp;i++){if(!v[i]){prime[++num]=i;v[i]=i;}for(int j=1;j<=num;j++){int now=prime[j];if(now>tp/i||now>v[i]) break;v[now*i]=now;}} } int calc(int x){int tp=floor(sqrt(x)),res=0;for(int i=1;i<=num;i++){int now=prime[i];if(now>tp) break;while(x%now==0){x/=now;res++;}}if(x>1) res++;return res; } ll a[N],b[N],c[N]; int main(){memset(fi,-1,sizeof(fi));find_prime();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++) ccnt[i]=calc(a[i]);s=n+1;t=s+1;for(int i=1;i<=n;i++){if(ccnt[i]%2==0) addline(s,i,b[i],0);else addline(i,t,b[i],0);}for(int i=1;i<=n;i++){if(ccnt[i]%2) continue;for(int j=1;j<=n;j++){if((a[i]%a[j]==0||a[j]%a[i]==0)&&abs(ccnt[i]-ccnt[j])==1) addline(i,j,2e18,-c[i]*c[j]);}}dinic();printf("%lld",flow);return 0; } /* 7 6 1 2 10000 2 3 10000 3 6 10000 1 4 8000 4 3 8000 2 5 6000 5 6 6000 */

總結

以上是生活随笔為你收集整理的YBTOJ洛谷P4068：数字配对（网络流）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。