正題

題目鏈接:https://www.luogu.com.cn/problem/P3705

---

題目大意

$n$對人，給出兩個(gè)$n?n$的矩形$a,b$。求一個(gè)$n$配對滿足$\frac{{\sum }_{i=1}^n{a}_{x_i,y_i}}{{\sum }_{i=1}^n{b}_{x_i,y_i}}$最大。

---

解題思路

很典型的$0/1$分?jǐn)?shù)規(guī)劃模型，直接上二分，然后剩下的就是一個(gè)最大費(fèi)用匹配因?yàn)閳D中滿足有最大匹配，上費(fèi)用流就行了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=210; const double inf=1e9,eps=1e-9; struct node{int to,next,w;double c; }a[N*N]; int n,s,t,tot,ls[N],A[N][N],B[N][N],mf[N],pre[N]; double f[N],answer;bool v[N];queue<int> q; void addl(int x,int y,int w,double c){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[tot].c=c;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;a[tot].c=-c;return; } bool spfa(){for(int i=0;i<=t;i++)f[i]=-inf;q.push(s);f[s]=0;mf[s]=inf;v[s]=1;while(!q.empty()){int x=q.front();v[x]=0;q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(a[i].w&&f[x]+a[i].c>f[y]){mf[y]=min(mf[x],a[i].w);f[y]=f[x]+a[i].c;pre[y]=i;if(!v[y])q.push(y),v[y]=1;}} }return f[t]>-inf; } void Update(){int x=t;while(x!=s){a[pre[x]].w-=mf[t];a[pre[x]^1].w+=mf[t];answer+=a[pre[x]].c*mf[t];x=a[pre[x]^1].to;}return; } bool check(double w){answer=0;tot=1;s=2*n+1;t=s+1;memset(ls,0,sizeof(ls));for(int i=1;i<=n;i++)addl(s,i,1,0),addl(i+n,t,1,0);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)addl(i,j+n,1,A[i][j]-B[i][j]*w);while(spfa())Update();return answer>=0; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&A[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&B[i][j]);double l=0,r=n*1e4;while(r-l>eps){double mid=(l+r)/2.0;if(check(mid))l=mid; else r=mid;}printf("%.6lf",(l+r)/2.0); }

總結(jié)

以上是生活随笔為你收集整理的P3705-[SDOI2017]新生舞会【0/1分数规划,费用流】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。