首页 > 代码库 > 【BZOJ4514】【SDOI2016】数字配对 [费用流]
【BZOJ4514】【SDOI2016】数字配对 [费用流]
数字配对
Time Limit: 10 Sec Memory Limit: 128 MB[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
Solution
显然是一个费用流，并且这可以是一个二分图，由于 ai/aj 要是质数，那显然可以根据质因子个数的奇偶分类。
然后跑一跑最大费用最大流。判断一下值要>=0即可统计入答案。mmpBearChild查了一个下午错，发现是INF开小了qaq。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 #include<map> 9 using namespace std; 10 typedef long long s64; 11 12 const int ONE = 205*205; 13 const int INF = 2147483640; 14 15 int n; 16 int a[ONE], b[ONE], c[ONE]; 17 s64 dist[ONE]; 18 int vis[ONE], q[ONE*10], pre[ONE]; 19 int first[ONE], go[ONE], next[ONE], pas[ONE], from[ONE], tot; 20 int pNum[ONE]; 21 int odd[ONE],Onum, eve[ONE],Enum; 22 int S, T, Ans; 23 int prime[ONE], isp[ONE], p; 24 s64 Val, w[ONE]; 25 26 int get() 27 { 28 int res=1,Q=1;char c; 29 while( (c=getchar())<48 || c>57 ) 30 if(c==‘-‘)Q=-1; 31 res=c-48; 32 while( (c=getchar())>=48 && c<=57 ) 33 res=res*10+c-48; 34 return res*Q; 35 } 36 37 void Getp(int MaxN) 38 { 39 for(int i=2; i <= MaxN; i++) 40 { 41 if(!isp[i]) prime[++p] = i; 42 for(int j=1; j <= prime[p], i*prime[j] <= MaxN; j++) 43 { 44 isp[i * prime[j]] = 1; 45 if(i % prime[j] == 0) break; 46 } 47 } 48 } 49 50 int Factor(int x) 51 { 52 int res = 0; 53 while(x != 1) 54 { 55 for(int i=1; i<=p; i++) 56 if(x % prime[i] == 0) 57 { 58 x /= prime[i]; 59 res++; 60 break; 61 } 62 } 63 return res; 64 } 65 66 int PD(int x, int y) 67 { 68 if(x > y) swap(x, y); 69 if(x==0 || y==0 || y%x!=0) return 0; 70 x = y / x; 71 for(int i=2; i<x; i++) 72 if(x % i == 0) return 0; 73 return 1; 74 } 75 76 int Add(int u, int v, int flow, s64 z) 77 { 78 next[++tot]=first[u]; first[u]=tot; go[tot]=v; pas[tot]=flow; w[tot]=z; from[tot]=u; 79 next[++tot]=first[v]; first[v]=tot; go[tot]=u; pas[tot]=0; w[tot]=-z; from[tot]=v; 80 } 81 82 bool Bfs() 83 { 84 for(int i=S; i<=T; i++) dist[i] = -1e18; 85 int tou = 0, wei = 1; 86 q[1] = S; vis[S] = 1; dist[S] = 0; 87 while(tou < wei) 88 { 89 int u = q[++tou]; 90 for(int e=first[u]; e; e=next[e]) 91 { 92 int v=go[e]; 93 if(dist[v] < dist[u] + w[e] && pas[e]) 94 { 95 dist[v] = dist[u] + w[e]; 96 pre[v] = e; 97 if(!vis[v]) 98 { 99 q[++wei] = v;100 vis[v] = 1;101 }102 }103 }104 vis[u] = 0;105 }106 return dist[T] != -1e18;107 }108 109 void Deal()110 {111 int x = INF;112 for(int e=pre[T]; e; e=pre[from[e]]) x = min(x, pas[e]);113 if(Val + dist[T] * x >= 0)114 {115 for(int e=pre[T]; e; e=pre[from[e]])116 {117 pas[e] -= x;118 pas[((e-1)^1)+1] += x;119 }120 Val += dist[T] * x;121 Ans += x;122 return;123 }124 printf("%d", Ans - Val / dist[T]);125 exit(0);126 }127 128 int main()129 {130 Getp(ONE);131 n = get();132 for(int i=1; i<=n; i++) a[i] = get(), pNum[i] = Factor(a[i]);133 for(int i=1; i<=n; i++) b[i] = get();134 for(int i=1; i<=n; i++) c[i] = get();135 136 S = 0; T = n+1;137 for(int i=1; i<=n; i++)138 {139 if(pNum[i] & 1) Add(S,i, b[i],0), odd[++Onum] = i;140 else Add(i,T, b[i],0), eve[++Enum] = i;141 }142 143 for(int i=1; i<=Onum; i++)144 for(int j=1; j<=Enum; j++)145 {146 int x = odd[i], y = eve[j];147 if( PD(a[x], a[y]) )148 Add(x,y, INF,(s64)c[x]*c[y]);149 }150 151 while(Bfs()) Deal();152 printf("%d", Ans - Val / dist[T]);153 }
【BZOJ4514】【SDOI2016】数字配对 [费用流]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。