首页 > 代码库 > 【BZOJ 3308】 3308: 九月的咖啡店 (费用流|二分图最大权匹配)
【BZOJ 3308】 3308: 九月的咖啡店 (费用流|二分图最大权匹配)
3308: 九月的咖啡店
Time Limit: 30 Sec Memory Limit: 128 MB
Submit: 244 Solved: 86Description
深绘里在九份开了一家咖啡让,如何调配咖啡民了她每天的头等大事
我们假设她有N种原料,第i种原料编号为i,调配一杯咖啡则需要在这
里若干种兑在一起。不过有些原料不能同时在一杯中,如果两个编号
为i,j的原料,当且仅当i与j互质时,才能兑在同一杯中。
现在想知道,如果用这N种原料来调同一杯咖啡,使用的原料编号之和
最大可为多少。Input
一个数字N
Output
如题
Sample Input
10
Sample Output
30
HINT
1<=N<=200000Source
【分析】
其实一开始也是认为每个质数自己搞成一个极大的数。
后来也发现大于$\sqrt n$可能是有问题的。
然后最i多只会有两个数,且一个大于$\sqrt n$,一个小于【这种东西还是靠胆量猜吧?或许可以证明?
可以先每个质数自己搞成一个极大的数,然后建二分图,
若a,b能配对
a,b连边 权值Vab?Va?Vb
【费用流ins也能打错的我。。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 #define Maxn 200010 9 #define Maxm 200010 10 #define INF 0xfffffff 11 #define LL long long 12 13 int mymin(int x,int y) {return x<y?x:y;} 14 15 struct node 16 { 17 int x,y,f,c,o,next; 18 }t[Maxm*2]; 19 int first[Maxn],len; 20 21 int st,ed; 22 void ins(int x,int y,int f,int c) 23 { 24 if(c<=0&&x!=st&&y!=ed) return; 25 t[++len].x=x;t[len].y=y;t[len].f=f;t[len].c=c; 26 t[len].next=first[x];first[x]=len;t[len].o=len+1; 27 t[++len].x=y;t[len].y=x;t[len].f=0;t[len].c=-c; 28 t[len].next=first[y];first[y]=len;t[len].o=len-1; 29 } 30 31 queue<int > q; 32 bool inq[Maxn]; 33 LL dis[Maxn],flow[Maxn]; 34 int pre[Maxn]; 35 bool bfs() 36 { 37 memset(inq,0,sizeof(inq)); 38 // memset(dis,63,sizeof(dis)); 39 for(int i=1;i<=ed;i++) dis[i]=-INF; 40 while(!q.empty()) q.pop(); 41 q.push(st);dis[st]=0;flow[st]=INF; 42 inq[st]=1; 43 while(!q.empty()) 44 { 45 int x=q.front(); 46 for(int i=first[x];i;i=t[i].next) if(t[i].f>0) 47 { 48 int y=t[i].y; 49 if(dis[y]<dis[x]+t[i].c) 50 { 51 dis[y]=dis[x]+t[i].c; 52 flow[y]=mymin(flow[x],t[i].f); 53 pre[y]=i; 54 if(!inq[y]) 55 { 56 inq[y]=1; 57 q.push(y); 58 } 59 } 60 } 61 q.pop();inq[x]=0; 62 } 63 return dis[ed]>-INF; 64 } 65 66 LL sum; 67 void max_flow() 68 { 69 while(bfs()) 70 { 71 if(dis[ed]<0) return; 72 sum+=flow[ed]*dis[ed]; 73 int x=ed; 74 while(x!=st) 75 { 76 t[pre[x]].f-=flow[ed]; 77 t[t[pre[x]].o].f+=flow[ed]; 78 x=t[pre[x]].x; 79 } 80 } 81 } 82 83 int n; 84 LL pri[Maxn];int pl; 85 LL as[Maxn]; 86 bool vis[Maxn]; 87 void init() 88 { 89 memset(vis,0,sizeof(vis)); 90 for(int i=2;i<=n;i++) 91 { 92 if(!vis[i]) pri[++pl]=i; 93 for(int j=1;j<=pl;j++) 94 { 95 if(i*pri[j]>n) break; 96 vis[i*pri[j]]=1; 97 if(i%pri[j]==0) break; 98 } 99 } 100 for(int i=1;i<=pl;i++) 101 { 102 as[i]=pri[i]; 103 while(as[i]*pri[i]<=n) as[i]*=pri[i]; 104 sum+=as[i]; 105 } 106 int i; 107 for(i=1;pri[i]*pri[i]<n&&i<=pl;i++) 108 for(int j=pl;pri[j]*pri[j]>=n;j--) 109 { 110 int x=pri[i]*pri[j]; 111 if(x>n) continue; 112 while(x*pri[i]<=n) x*=pri[i]; 113 ins(i,j,1,x-as[i]-as[j]); 114 } 115 st=pl+1;ed=st+1; 116 for(int i=1;pri[i]*pri[i]<n&&i<=pl;i++) 117 ins(st,i,1,0); 118 for(int i=pl;pri[i]*pri[i]>=n;i--) ins(i,ed,1,0); 119 } 120 121 int main() 122 { 123 len=0; 124 memset(first,0,sizeof(first)); 125 sum=0; 126 scanf("%d",&n); 127 init(); 128 max_flow(); 129 printf("%lld\n",sum+1); 130 return 0; 131 }
有些东西不开LL会WA掉。
2017-04-13 07:24:50
【BZOJ 3308】 3308: 九月的咖啡店 (费用流|二分图最大权匹配)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。