「SDOI2017」新生舞会 - 分数规划+二分图最大权匹配

题目大意

    学校组织了一次新生舞会，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,\ldots,a’_n$，假设每对舞伴的不协调程度分别是$b’_1,b’_2,\ldots,b’_n$。令$C=\frac{a’_1+a’_2+\ldots+a’_n}{b’_1+b’_2+\ldots+b’_n}$,Cathy希望$C$值最大。

---

题目分析

答案是分数形式，不难想到分数规划。
设

$$\lambda=\frac{a'_1+a'_2+\ldots+a'_n}{b'_1+b'_2+\ldots+b'_n}$$

则：

$$\lambda(b'_1+b'_2+\ldots+b'_n)=a'_1+a'_2+\ldots+a'_n$$ $$a'_1-\lambda b'_1+\ldots+a'_n-\lambda b'_n=0$$

因此二分$\lambda$将$a’_i-\lambda b’_i$作为权值进行最大权匹配，若答案$\gt0$说明$\lambda$较小，反之说明$\lambda$较大。

因为是实数费用，用zkw费用流会被卡，于是写了EK。
用KM的就不提了。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=205;
const double eps=1e-8;

int dcmp(double x) {
	if(fabs(x)<=eps)return 0;
	if(x>eps)return 1;
	return -1;
}

struct Edge {
	int from,to,cap,flow;
	double cost;
	Edge(int x=0,int y=0,int c=0,int f=0,double co=0):from(x),to(y),cap(c),flow(f),cost(co) {}
};

struct MinimumCost_MaximumFlow { //EK Edition
	int n,m;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool inque[maxn];
	int a[maxn],path[maxn];
	double dist[maxn];
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	void AddEdge(int x,int y,int v,double f) {
		edges.push_back(Edge(x,y,v,0,f));
		edges.push_back(Edge(y,x,0,0,-f));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
	}
	bool bellmanford(int s,int t,int& flow,double& cost) {
		for(int i=1; i<=n; i++)dist[i]=-1e18;
		memset(inque,0,sizeof(inque));
		queue<int>Q;
		Q.push(s);
		dist[s]=path[s]=0;
		a[s]=INT_MAX;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop();
			inque[Now]=0;
			for(int id:G[Now]) {
				Edge& e=edges[id];
				int Next=e.to;
				if(e.cap>e.flow&&dcmp(dist[Next]-dist[Now]-e.cost)<0) {
					dist[Next]=dist[Now]+e.cost;
					path[Next]=id;
					a[Next]=min(a[Now],e.cap-e.flow);
					if(!inque[Next]) {
						Q.push(Next);
						inque[Next]=1;
					}
				}
			}
		}
		if(dist[t]==-1e18)return false;
		flow+=a[t];
		cost+=dist[t]*a[t];
		for(int Now=t; Now!=s; Now=edges[path[Now]].from) {
			edges[path[Now]].flow+=a[t];
			edges[path[Now]^1].flow-=a[t];
		}
		return true;
	}
	int maxflow(int s,int t,double& cost) {
		int flow=0;
		cost=0;
		while(bellmanford(s,t,flow,cost));
		return flow;
	}
} mcmf;

int n;
double a[105][105],b[105][105];

bool Check(double x) {
	int S=2*n+1,T=2*n+2;
	mcmf.init(T);
	for(int i=1; i<=n; i++) {
		mcmf.AddEdge(S,i,1,0);
		mcmf.AddEdge(n+i,T,1,0);
	}
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			mcmf.AddEdge(i,n+j,1,a[i][j]-b[i][j]*x);
	double cost=0;
	mcmf.maxflow(S,T,cost);
	return cost>eps;
}

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			a[i][j]=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			b[i][j]=Get_Int();
	double Left=0,Right=1e6;
	while(Right-Left>eps) {
		double mid=(Left+Right)/2;
		if(Check(mid))Left=mid;
		else Right=mid;
	}
	printf("%0.6lf\n",Right);
	return 0;
}