题面

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

 题解

+网络流

二分答案mid，将每个点的值看作a-b*mid。

这题考虑对于每一个mid，求出最大方案

由于每个男生只能搭配一名不同的女生，所以问题可以转化为：1个n*n的矩阵中每个位置都有1个数，求选出n个彼此不在同一行或同一列的数的和的最大值是多少。

加边$s->i(1,0),i+n->t(1,0)，i->j+n(1，v[i][j])$，跑最大费用最大流，结果其实就是$sum(a_i)-a*sum(b_i)$

 代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N=50000,st=N-9,ed=N-8;
#define inf 10000
#define rev(i) (((i-1)^1)+1)
int head[N],cnt,to[N],nxt[N],n,m,cap[N],lev[N];
double cost[N],dis[N],ans;
bool vis[N],vis2[N];
void connect(int a,int b,int d,double c)
{
    to[++cnt]=b,cost[cnt]=c,cap[cnt]=d,nxt[cnt]=head[a],head[a]=cnt;
    to[++cnt]=a,cost[cnt]=-c,cap[cnt]=0,nxt[cnt]=head[b],head[b]=cnt;
}
bool spfa()
{
    queue q;
    memset(lev,0,sizeof(lev));
    for(int i=1;i0;
}
signed main()
{
	int tot=0;
	cin>>n;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&val[i][j]),tot+=val[i][j];
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&weight[i][j]);
	double l=0,r=tot;
	while(r-l>0.0000005)
	{
		double mid=(l+r)/2.0;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%.6f",l);
}