2018.08.28 九份的咖啡店（费用流）

描述

深绘里在九份开了一家咖啡店。当然如何调配咖啡成了她每天的头等大事。 我们假设她有 n 种原料，第 i 种原料编号为 i，而调配一杯咖啡则需要选择这里面的若干种来兑在一起。
不过有些原料不能同时调兑在同一杯里。如果两个编号为 i， j 的原料，当且仅当 i 和 j 互质时，它们才能被兑在同一杯里。
现在深绘里想知道，如果她用这 n 种原料来调兑一杯咖啡，那么这杯咖啡所使用的原料编号之和最大能为多少呢？ …

输入

一行，一个正整数 n

输出

一行一个正整数，即最大的编号之和

样例输入

10

样例输出

30

提示

【数据范围和约定】

对于 20% 的数据， 1 ≤ n ≤ 30
对于 50% 的数据， 1 ≤ n ≤ 200
对于 80% 的数据， 1 ≤ n ≤ 800 对于 100% 的数据， 1 ≤ n ≤ 200000

标签

湖南2013省选模拟

spfa写错了也很感动。。。
有一个神仙结论：原料最多由两种质因数组成，且一个小于sqrt(n)，一个大于sqrt(n)（本蒟蒻并不会证明）。
知道这个结论之后就可以跑最大费用流了。
代码：

#include
#define N 1000005
#define inf 1000000000
#define ll long long
using namespace std;
int n,pot[N],first[N],d[N],cnt=-1,prime[N],vis[N],in[N],pred[N],tot=0,ans,res;
struct edge{int c,w,v,next;}e[N<<1];
inline void add_edge(int u,int v,int c,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].c=c,e[cnt].next=first[u],first[u]=cnt;}
inline void add(int u,int v,int c,int w){add_edge(u,v,c,w),add_edge(v,u,0,-w);}
inline void init(){for(int i=2;i<=n;++i){if(!vis[i])prime[++tot]=i;for(int j=1;j<=tot;++j){if(prime[j]*i>n)break;vis[prime[j]*i]=1;if(i%prime[j]==0)break;}}
}
inline void calc(int s,int t){int pos=t;while(pos!=s){e[pred[pos]].c-=1;e[pred[pos]^1].c+=1;pos=e[pred[pos]^1].v;}
}
inline bool spfa(int s,int t){queue<int>q;memset(d,128,sizeof(d));ll tmp=d[0];for(int i=1;i<=t;++i)in[i]=0;in[s]=1,q.push(s),d[s]=0;while(!q.empty()){int x=q.front();q.pop();for(int i=first[x];~i;i=e[i].next){int v=e[i].v;if(d[v]if(!in[v])in[v]=1,q.push(v);}}in[x]=0;}if(d[t]==tmp)return false;calc(s,t);ans+=d[t];res=max(res,ans);return true;
}
inline int solve(int x,ll tmp){while(1){tmp*=x;if(tmp*x>n)break;}return tmp;
}
int main(){memset(first,-1,sizeof(first));scanf("%d",&n),init();int pos=0;ll sum=0;for(int i=1;i<=tot;++i){sum+=(ll)solve(prime[i],1);if(1ll*prime[i]*(1ll*prime[i])>n)add(1,i+1,1,0);else add(i+1,tot+10,1,0),pos=i;}for(int i=pos+1;i<=tot;++i)for(int j=1;j<=pos;++j){int tmp=solve(prime[j],prime[i]),ttmp=solve(prime[j],1);if(tmp>n)continue;add(i+1,j+1,1,tmp-ttmp-solve(prime[i],1));}while(spfa(1,tot+10));cout<<1ll*(res+sum+1);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！