题解 P3705 [SDOI2017]新生舞会

分析

做了几道分数规划题，选一些来写题解。

首先观察答案形式，就是求最终 \((\dfrac{\sum a_i'}{\sum b_i'})\geqslant ans\) 最大的 \(ans\)，在转化一下形式，就是 \(\sum a_i'-ans\times b_i'\geqslant 0\)。

所以我们去二分答案（显然越小的答案最终越容易使上面式子满足），然后每一组对答案的贡献就能计算出，然后又要求每一个人都要找到各自舞伴，式子中的大于等于可以视为使左边的值最大，所以在 check 函数中我们男女生建点，每一组的贡献用作建边，男生向女生建边，流量为 \(1\)，费用 \(a[i][j]-mid\times b[i][j]\)，超级源点向男生，女生向超级汇点建流量 \(1\)，费用 \(0\) 的边，验证最大费用是否大于等于 \(0\) 即可。

代码

#include
using namespace std;
inline void read(int &res){
	res=0;
	int f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')res=(res<<1)+(res<<3)+c-48,c=getchar();
	res*=f;
}
int n,s,t;
int a[105][105];
int b[105][105];
int head[210],tot;
struct edge{
	int to,nex,w;
	double bq;
}e[100000];
inline void add(int qq,int mm,int w,double bq){
	e[++tot].to=mm;
	e[tot].nex=head[qq];
	e[tot].w=w;
	e[tot].bq=bq;
	head[qq]=tot;
}
double dis[210];
int pre[210],incf[210];
queueq;
int vis[210];
bool spfa(){
	for(int i=1;i<=t;i++){
		dis[i]=-1e18;
		incf[i]=1e9;
	}
	q.push(s);
	while(q.size()){
		int x=q.front();q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=e[i].nex){
			if(!e[i].w)continue;
			int v=e[i].to;
			if(dis[v]=0;
}
int main()
{
	read(n);
	s=0;t=2*n+1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)read(a[i][j]);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)read(b[i][j]);
	}
	double l=0,r=10000;
	while(r-l>=1e-7){
		double mid=(l+r)/2.0;
		if(check(mid))l=mid+1e-8;
		else r=mid-1e-8;
	}
	printf("%.6lf",l);
}