luoguP3705 [SDOI2017]新生舞会

Isonan

2018-08-11 23:33:00

Solution

原题传送门[>Here<](https://www.luogu.org/problemnew/show/P3705) 我的01分数规划学习笔记[>Here<](https://www.luogu.org/blog/PopulusEuphratica/post-xue-xi-bi-ji-01-fen-shuo-gui-hua) 这道题是道比较有趣的01分数规划题,不仅需要01分数规划的思想,还要应用网络流求解,有一些复杂。 考虑对于二分出的每一个值,我们都可以网络流建图: 从源点向所有男生建边,流为1,费用为0; 从男生向女生建边,流为1,费用为$mid*b_{ij}-a_{ij}$; 从女生向汇点建边,流为1,费用为0。 接下来跑一遍最小费用最大流求出匹配的最小费用,判断是否是负数就可以了。 这题还需要卡一点常,也算是考验下应试技巧。 代码: ```cpp #include <cstdio> #include <cstring> #define min(X,Y) ((X)<(Y)?(X):(Y)) int n,head[301],nxt[180001],b[180001],v[180001],k=1; int vt[180001],flow[301],q[100001],h,t,S,T,pre[301]; double dis[301],ct[180001],bene[180001],cost[180001],a[101][101],bad[101][101],tem,l=0.0,r=100000000.0,mid; bool inq[301]; void push(int s,int t,int val,double c){ nxt[++k]=head[s]; head[s]=k; b[k]=t; v[k]=val; cost[k]=c; } void link(int s,int t,int val,double c){ push(s,t,val,c); push(t,s,0,-c); } bool spfa(){ for(int i=S;i<=T;i++)dis[i]=1000000000.0; h=t=0; q[++t]=S; inq[S]=1; dis[S]=0.0; flow[S]=0x7f7f7f7f; while(h<t){ ++h;inq[q[h]]=0; for(register int i=head[q[h]];i;i=nxt[i]) if(dis[b[i]]>dis[q[h]]+cost[i]&&v[i]){ dis[b[i]]=dis[q[h]]+cost[i]; flow[b[i]]=min(flow[q[h]],v[i]); pre[b[i]]=i; if(!inq[b[i]])inq[b[i]]=1,q[++t]=b[i]; } } return dis[T]!=1000000000.0; } bool judge(double u){ double ans=0.0; memset(head,0,sizeof head); k=1; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) link(i,j+n,1,u*bad[i][j]-a[i][j]); link(S,i,1,0.0); link(i+n,T,1,0.0); } while(spfa()){ int tem=T; while(tem!=S){ v[pre[tem]]-=flow[T]; v[pre[tem]^1]+=flow[T]; tem=b[pre[tem]^1]; } ans+=(double)flow[T]*dis[T]; } return ans<0.0; } int read(){ int x=0; char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x; } int main(){ n=read(); T=n+n+1; for(register int i=1;i<=n;i++) for(register int j=1;j<=n;j++) a[i][j]=(double)read(); for(register int i=1;i<=n;i++) for(register int j=1;j<=n;j++) bad[i][j]=(double)read(); while(r-l>=0.000000001){ mid=(l+r)/2; if(judge(mid))l=mid; else r=mid; } printf("%.6lf",l); } ```