首页 > 代码库 > [Sdoi2016]数字配对
[Sdoi2016]数字配对
Submit: 1411 Solved: 535
[Submit][Status][Discuss]
Description
有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。
若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数，
那么这两个数字可以配对，并获得 ci×cj 的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。
Input
第一行一个整数 n。
第二行 n 个整数 a1、a2、……、an。
第三行 n 个整数 b1、b2、……、bn。
第四行 n 个整数 c1、c2、……、cn。
Output
一行一个数，最多进行多少次配对
Sample Input
3
2 4 8
2 200 7
-1 -2 1
2 4 8
2 200 7
-1 -2 1
Sample Output
4
HINT
n≤200，ai≤10^9，bi≤10^5，∣ci∣≤10^5
Source
鸣谢Menci上传
思路：二分图染色+重新构造二分图+最小费用最大流
代码实现：
1 #include<cstdio> 2 #include<cstring> 3 #define LL long long 4 #define inf 1000000000000000ll 5 LL n,s,t,nf,sf,nw,sw; 6 int a,b,l; 7 LL sa[210],sb[210],sc[210]; 8 LL ret; 9 char ch[30]; 10 int h[210],hs=1; 11 struct edge{int s,n;LL w,f;}e[900000]; 12 bool pf,v[210],map[210][210]; 13 int ca[210],as,cb[210],bs; 14 LL f[210]; 15 int q[900000],head,tail; 16 struct place{int q,l;}p[900000]; 17 inline LL min(LL x,LL y){return x<y?x:y;} 18 LL read(){ 19 ret=pf=0,l=1; 20 do{ch[0]=getchar();}while((ch[0]<‘0‘||ch[0]>‘9‘)&&ch[0]!=‘-‘); 21 if(ch[0]==‘-‘) pf=1,ch[0]=getchar(); 22 do{ch[l++]=getchar();}while(ch[l-1]>=‘0‘&&ch[l-1]<=‘9‘); 23 l-=2; 24 for(LL i=l,j=1;i>=0;i--,j*=10) ret+=(ch[i]-‘0‘)*j; 25 if(pf) ret*=-1; 26 return ret; 27 } 28 void write(LL x){ 29 if(!x) return; 30 write(x/10); 31 putchar(x%10+‘0‘); 32 } 33 bool ps(int x){ 34 for(int i=2;i*i<=x;i++) 35 if(x%i==0) return 0; 36 return 1; 37 } 38 void dye(int x,int k){ 39 v[x]=1; 40 if(k==2) ca[as++]=x; 41 else cb[bs++]=x; 42 for(int i=h[x];i;i=e[i].n) 43 if(!v[e[i].s]) dye(e[i].s,k^1); 44 } 45 LL SPFA(){ 46 for(int i=s;i<=t;i++) f[i]=inf; 47 head=tail=0; 48 q[head++]=s,f[s]=0; 49 while(head>tail){ 50 a=q[tail++]; 51 for(int i=h[a];i;i=e[i].n) 52 if(e[i].w&&f[a]+e[i].f<f[e[i].s]){ 53 f[e[i].s]=f[a]+e[i].f; 54 q[head++]=e[i].s; 55 p[e[i].s]=(place){a,i}; 56 } 57 } 58 return f[t]; 59 } 60 LL AP(int k,LL w){ 61 if(k==s) return w; 62 int re=AP(p[k].q,min(w,e[p[k].l].w)); 63 e[p[k].l].w-=re; 64 e[p[k].l^1].w+=re; 65 return re; 66 } 67 bool Dinic(){ 68 nf=SPFA(); 69 if(nf==inf) return 0; 70 nw=AP(t,inf); 71 if(nf<=0) sw+=nw; 72 else sw+=min(nw,-sf/nf); 73 sf+=nf*nw; 74 if(sf>0) return 0; 75 else return 1; 76 } 77 int main(){ 78 n=read(); 79 s=0,t=n+1; 80 for(int i=1;i<=n;i++) sa[i]=read(); 81 for(int i=1;i<=n;i++) sb[i]=read(); 82 for(int i=1;i<=n;i++) sc[i]=read(); 83 for(int i=1;i<=n;i++) 84 for(int j=1;j<=n;j++) 85 if(sa[j]&&sa[i]%sa[j]==0&&ps(sa[i]/sa[j])){ 86 e[++hs]=(edge){j,h[i]},h[i]=hs; 87 e[++hs]=(edge){i,h[j]},h[j]=hs; 88 map[i][j]=map[j][i]=1; 89 } 90 for(int i=1;i<=n;i++) if(!v[i]) dye(i,2); 91 memset(h,0,sizeof(h)),hs=1; 92 for(int i=0;i<as;i++) 93 for(int j=0;j<bs;j++) 94 if(map[ca[i]][cb[j]]){ 95 a=ca[i],b=cb[j]; 96 e[++hs]=(edge){b,h[a],min(sb[a],sb[b]),-sc[a]*sc[b]},h[a]=hs; 97 e[++hs]=(edge){a,h[b],0,sc[a]*sc[b]},h[b]=hs; 98 } 99 for(int i=0;i<as;i++) a=ca[i],e[++hs]=(edge){a,h[s],sb[a],0},h[s]=hs++;100 for(int i=0;i<bs;i++) b=cb[i],e[++hs]=(edge){t,h[b],sb[b],0},h[b]=hs++;101 while(Dinic());102 write(sw);103 return 0;104 }
100+的网络流，还不带高级数据结构，呵呵。
还有long long神烦。
题目来源：bzoj
[Sdoi2016]数字配对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。