首页 > 代码库 > BZOJ 4819 新生舞会
BZOJ 4819 新生舞会
第一句话:算出3.363636的孩子啊，你跑错流种了。
貌似上一篇我讲SDOI出原题？嘿还真是！
半个月前有一个叫WG的男人给我们搞过一场考试... ...
里面有一道题叫做保密... ...SDOI2011... ...
对于每个点求ΣS/ΣT最值然后转跑浮点数网络流... ...
是不是感觉我在讲这道题的正解... ...没错正解就是这样... ...所以我说是原题吧。
跟 保密 是一样的思路。求Σa/Σb的最值，可以用二分答案来做。
Σa/Σb的最大值怎么求呢？设一个当前答案ans;
显然如果有方案使Σa/Σb>ans则答案更优。
把式子化一下得：
Σa>Σb*ans;
即
Σa-Σb*ans>0;
即
Σ(a-b*ans)>0;
每次重新建图或者带着二分的mid跑最大费用最大流即可。
没错跑出3.363636是跑的最小费用最大流... ...别问我怎么知道的。
用KM算法算最大权匹配跑的更快奈何我不会。好在它是一个左右相等的完全二分图，用费用流做也是可以的。
出题人良心发现没有卡费用流真是资磁。
还有就是浮点数二分答案跟整数不一样，要用eps。
有哪位大佬能够告诉我 为什么我的费用流 跑的那么慢吗？
#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <queue>#include <cstring>#define LL long long#define dob doubleusing namespace std; const int N = 110;const int M = 100010;const dob eps = 1e-7;const dob dobInf = 19260817.2333;struct Node{int to,C;double val;int next;}E[M];int head[M],tot,n,S,T,up[M],In[M];dob a[N][N],b[N][N],far[M],Ans; int gi(){ int x=0,res=1;char ch=getchar(); while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)res=-res;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-48,ch=getchar(); return x*res;} inline void link(int u,int v,int c,double val){ E[++tot]=(Node){v,c,val,head[u]}; head[u]=tot; E[++tot]=(Node){u,0,-val,head[v]}; head[v]=tot;} inline void slink(double Eps){ memset(head,0,sizeof(head));tot=1; for(int i=1;i<=n;++i) { link(S,i,1,0.0000000); link(i+n,T,1,0.0000000); for(int j=1;j<=n;++j) link(i,n+j,1,(a[i][j])-Eps*b[i][j]); }}inline bool spfa(){ for(int i=0;i<=T;++i) far[i]=-dobInf; memset(up,0,sizeof(up)); queue<int>Q;Q.push(S); far[S]=0.000000;In[S]=1; while(!Q.empty()) { int x=Q.front();Q.pop(); for(int e=head[x];e;e=E[e].next) if(E[e].C && far[x]+E[e].val>far[E[e].to]) { up[E[e].to]=e; far[E[e].to]=far[x]+E[e].val; if(!In[E[e].to]) Q.push(E[e].to),In[E[e].to]=1; } In[x]=0; } if(!up[T])return false; for(int i=T;i^S;i=E[up[i]^1].to) E[up[i]].C--,E[up[i]^1].C++; Ans-=far[T];return true;} inline bool check(){ Ans=0.00; while(spfa()) if(Ans>=0.00)return true; return Ans>=0.00;} int main(){ n=gi();S=2*n+1,T=2*n+2; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%lf",&a[i][j]); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%lf",&b[i][j]); dob l=0.0,r=10000,ans=r; while(r-l>eps) { double mid=(l+r)/2.0; slink(mid); if(check())r=mid,ans=mid; else l=mid; } printf("%.6lf\n",ans); return 0;}
BZOJ 4819 新生舞会
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。