bzoj4514[Sdoi2016]數(shù)字配對(duì)

題意：

有 n 種數(shù)字，第 i 種數(shù)字是 ai、有 bi 個(gè)，權(quán)值是 ci。若兩個(gè)數(shù)字 ai、aj 滿足ai 是 aj 的倍數(shù)且 ai/aj 是一個(gè)質(zhì)數(shù)，那么這兩個(gè)數(shù)字可以配對(duì)，并獲得 ci×cj 的價(jià)值。一個(gè)數(shù)字只能參與一次配對(duì)，可以不參與配對(duì)。在獲得的價(jià)值總和不小于 0 的前提下，求最多進(jìn)行多少次配對(duì)。

題解：

費(fèi)用流。本題難點(diǎn)是每個(gè)數(shù)字只能參加一次配對(duì)，很容易建錯(cuò)圖。正解是先對(duì)每個(gè)數(shù)字分解質(zhì)因數(shù)，按照質(zhì)因數(shù)個(gè)數(shù)的奇偶建二分圖。原因是質(zhì)因數(shù)奇數(shù)個(gè)和質(zhì)因數(shù)偶數(shù)個(gè)的兩個(gè)數(shù)相除的商必定不是質(zhì)數(shù)，巧妙地解決了問(wèn)題。在判斷質(zhì)數(shù)方面，如果樸素判斷肯定會(huì)T，所以可以先篩法求一個(gè)質(zhì)數(shù)表，判斷的時(shí)候直接枚舉能否整除質(zhì)數(shù)。因?yàn)椤?09≤32000，所以質(zhì)數(shù)表只要到32000就行了。不過(guò)時(shí)間復(fù)雜度我不會(huì)算，本弱太弱了！

題解：

1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #include <queue> 6 #define inc(i,j,k) for(ll i=j;i<=k;i++) 7 #define ll long long 8 #define INF 10000000000000000 9 using namespace std; 10 11 ll p[32000],cnt,mx; bool vis1[32000]; 12 void getprime(){ 13 cnt=0; memset(vis1,0,sizeof(vis1)); inc(i,2,(ll)sqrt(mx))if(! vis1[i]){ 14 p[++cnt]=i; for(ll j=i;j<=(ll)sqrt(mx);j+=i)vis1[j]=1; 15 } 16 } 17 inline bool is_prime(ll x){ 18 if(x==1)return 0; 19 inc(i,1,cnt){if(p[i]*p[i]>x)return 1; if(x%p[i]==0)return 0;} 20 } 21 struct e{int f,t;ll c,w;int n;}; e es[1000000]; int ess,g[1000]; 22 inline void pe(int f,int t,ll c,ll w){ 23 es[++ess]=(e){f,t,c,w,g[f]}; g[f]=ess; es[++ess]=(e){t,f,0,-w,g[t]}; g[t]=ess; 24 } 25 void init(){ess=-1; memset(g,-1,sizeof(g));} 26 queue <int> q; ll d[1000],cost,flow; int fr[1000]; bool inq[1000],vis2[1000]; 27 bool spfa(int s,int t){ 28 while(! q.empty())q.pop(); memset(vis2,0,sizeof(vis2)); memset(inq,0,sizeof(inq)); 29 q.push(s); vis2[s]=1; inq[s]=1; d[s]=0; 30 while(! q.empty()){ 31 int x=q.front(); q.pop(); inq[x]=0; 32 for(int i=g[x];i!=-1;i=es[i].n)if(es[i].c&&(!vis2[es[i].t]||d[es[i].t]<d[x]+es[i].w)){ 33 vis2[es[i].t]=1; d[es[i].t]=d[x]+es[i].w; fr[es[i].t]=i; 34 if(!inq[es[i].t])q.push(es[i].t),inq[es[i].t]=1; 35 } 36 } 37 if(!vis2[t])return 0;else return 1; 38 } 39 ll maxflowmaxcost(int s,int t){ 40 flow=0; cost=0; 41 while(spfa(s,t)){ 42 ll a=INF,b=0;for(int i=t;i!=s;i=es[fr[i]].f)a=min(a,es[fr[i]].c); 43 for(int i=t;i!=s;i=es[fr[i]].f)es[fr[i]].c-=a,es[fr[i]^1].c+=a,b+=es[fr[i]].w; cost+=b*a; flow+=a; 44 if(cost<0){flow-=(cost%b==0?cost/b:cost/b+1); break;} 45 } 46 return flow; 47 } 48 ll a[1000],b[1000],c[1000];int n,s,t,sing[1000],doub[1000],tot,singn,doubn; 49 int main(){ 50 scanf("%d",&n); inc(i,1,n)scanf("%lld",&a[i]),mx=max(mx,a[i]); 51 inc(i,1,n)scanf("%lld",&b[i]); inc(i,1,n)scanf("%lld",&c[i]); 52 getprime(); s=0; t=n+1; singn=0; doubn=0; 53 inc(i,1,n){ 54 int x=a[i]; tot=0; inc(j,1,cnt)if(x%p[j]==0){ 55 while(x%p[j]==0)x/=p[j],tot++; if(x==1)break; 56 } 57 if(tot&1)sing[++singn]=i;else doub[++doubn]=i; 58 } 59 init(); inc(i,1,singn)pe(s,sing[i],b[sing[i]],0); inc(i,1,doubn)pe(doub[i],t,b[doub[i]],0); 60 inc(i,1,singn)inc(j,1,doubn) 61 if(max(a[sing[i]],a[doub[j]])%min(a[sing[i]],a[doub[j]])==0&&is_prime(max(a[sing[i]],a[doub[j]])/min(a[sing[i]],a[doub[j]]))) 62 pe(sing[i],doub[j],INF,c[sing[i]]*c[doub[j]]); 63 printf("%lld",maxflowmaxcost(s,t)); 64 return 0; 65 }

?

20160422

轉(zhuǎn)載于:https://www.cnblogs.com/YuanZiming/p/5703289.html

總結(jié)

以上是生活随笔為你收集整理的bzoj4514[Sdoi2016]数字配对的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。