[bzoj4819][01分数规划][网络流-费用流]新生舞会

本文主要是介绍[bzoj4819][01分数规划][网络流-费用流]新生舞会，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

学校组织了一次新生舞会，Cathy作为经验丰富的老学姐，负责为同学们安排舞伴。有n个男生和n个女生参加舞会
买一个男生和一个女生一起跳舞，互为舞伴。Cathy收集了这些同学之间的关系，比如两个人之前认识没计算得出 a[i][j]
，表示第i个男生和第j个女生一起跳舞时他们的喜悦程度。Cathy还需要考虑两个人一起跳舞是否方便，比如身高体重差别会不会太大，计算得出
b[i][j]，表示第i个男生和第j个女生一起跳舞时的不协调程度。当然，
还需要考虑很多其他问题。Cathy想先用一个程序通过a[i][j]和b[i][j]求出一种方案，再手动对方案进行微调。C
athy找到你，希望你帮她写那个程序。一个方案中有n对舞伴，假设没对舞伴的喜悦程度分别是a’1,a’2,…,a’n，
假设每对舞伴的不协调程度分别是b’1,b’2,…,b’n。令
C=(a’1+a’2+…+a’n)/(b’1+b’2+…+b’n),Cathy希望C值最大。

Input

第一行一个整数n。接下来n行，每行n个整数，第i行第j个数表示a[i][j]。
接下来n行，每行n个整数，第i行第j个数表示b[i][j]。 1<=n<=100,1<=a[i][j],b[i][j]<=10^4

Output

一行一个数，表示C的最大值。四舍五入保留6位小数，选手输出的小数需要与标准输出相等

Sample Input

3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9

Sample Output

5.357143

题解

2333新东西分数规划。早就想学了那就KOI之前学一学吧
口胡一下
设求出来的a[i][j]为A数组，b[i][j]为B数组
那么要求sigma(A[i])/sigma(B[i])最大
设当前找到了一个更优解k
于是sigma(A[i])/sigma(B[i])<=k
那么sigma(A[i])-sigma(B[i])*k<=0
拆掉式子可以变成sigma(A[i]-B[i]*k)<=0
找到左边的最大值，看看是不是小于0，小于零就证明找到了更优的解
对于这道题，我们直接二分答案。设二分答案为mid，每条边的边权就为a[i][j]-mid*b[i][j]，然后最大费用最大流验证答案
卡了一下精度1e-7，特别慢。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const double eps=0.0000001;
struct node
{int x,y,c,next,other;double d;
}a[210000];int len,last[1100];
void ins(int x,int y,int c,double d)
{int k1,k2;k1=++len;a[len].x=x;a[len].y=y;a[len].c=c;a[len].d=d;a[len].next=last[x];last[x]=len;k2=++len;a[len].x=y;a[len].y=x;a[len].c=0;a[len].d=-d;a[len].next=last[y];last[y]=len;a[k1].other=k2;a[k2].other=k1;
}
queue<int> q;
int n;
bool v[1100];
double d[1100];int st,ed;
int pre[1100],tmp[1100];
bool spfa()
{for(int i=1;i<=n*2+2;i++)d[i]=-999999999.0;d[st]=0;memset(v,false,sizeof(v));v[st]=true;q.push(st);while(!q.empty()){int x=q.front();for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(d[y]<d[x]+a[k].d && a[k].c>0){d[y]=d[x]+a[k].d;pre[y]=x;tmp[y]=k;if(v[y]==false){v[y]=true;q.push(y);}}}q.pop();v[x]=false;}if(d[ed]!=-999999999.0)return true;return false;
}
bool mcf()
{double ans=0;while(spfa()){int x=ed,minn=999999999;while(x!=st){int k=tmp[x];minn=min(minn,a[k].c);x=pre[x];}x=ed;while(x!=st){int k=tmp[x];a[k].c-=minn;a[a[k].other].c+=minn;x=pre[x];}ans+=d[ed]*minn;}if(ans<=0)return false;return true;
}
double c1[110][110],c2[110][110];
bool check(double p)
{len=0;memset(last,0,sizeof(last));for(int i=1;i<=n;i++)ins(st,i,1,0);for(int i=1;i<=n;i++)ins(i+n,ed,1,0);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ins(i,j+n,1,c1[i][j]-p*c2[i][j]);if(mcf())return true;return false;
}
int main()
{scanf("%d",&n);int sum=0;st=n*2+1;ed=n*2+2;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lf",&c1[i][j]),sum+=c1[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lf",&c2[i][j]);double l=0.0,r=sum,ans;while(l+eps<=r){double mid=(l+r)/2;if(check(mid)){l=mid;ans=mid;}else r=mid;}printf("%.6lf\n",ans);return 0;
}