loj2003 「SDOI2017」新生舞会

分数规划+KM 算法

这个KM不好，看算法竞赛进阶指南的

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

int n, aa[105][105], bb[105][105], mat[105];

double a[105][105], exu[105], exv[105], sla[105];

const double eps=1e-8;

bool viu[105], viv[105];

bool dfs(int x){

	viu[x] = true;

	for(int i=1; i<=n; i++){

		if(viv[i])  continue;

		double gap=exu[x]+exv[i]-a[x][i];

		if(fabs(gap)<eps){

			viv[i] = true;

			if(!mat[i] || dfs(mat[i])){

				mat[i] = x;

				return true;

			}

		}

		else    sla[i] = min(sla[i], gap);

	}

	return false;

}

bool chk(double lim){

	memset(exv, 0, sizeof(exv));

	memset(mat, 0, sizeof(mat));

	for(int i=1; i<=n; i++){

		exu[i] = -1e99;

		for(int j=1; j<=n; j++){

			a[i][j] = aa[i][j] - lim * bb[i][j];

			exu[i] = max(exu[i], a[i][j]);

		}

	}

	for(int i=1; i<=n; i++){

		memset(sla, 127, sizeof(sla));

		while(true){

			memset(viu, 0, sizeof(viu));

			memset(viv, 0, sizeof(viv));

			if(dfs(i))  break;

			double tmp=1e99;

			for(int j=1; j<=n; j++)

				if(!viv[j])

					tmp = min(tmp, sla[j]);

			for(int j=1; j<=n; j++){

				if(viu[j])  exu[j] -= tmp;

				if(viv[j])  exv[j] += tmp;

				else    sla[j] -= tmp;

			}

		}

	}

	double tmp=0.0;

	for(int i=1; i<=n; i++)

		tmp += a[mat[i]][i];

	return tmp>-eps;

}

int main(){

	cin>>n;

	for(int i=1; i<=n; i++)

		for(int j=1; j<=n; j++)

			scanf("%d", &aa[i][j]);

	for(int i=1; i<=n; i++)

		for(int j=1; j<=n; j++)

			scanf("%d", &bb[i][j]);

	double l=0.0, r=1000000.0, mid;

	while(fabs(r-l)>eps){

		mid = (l + r) / 2.0;

		if(chk(mid))	l = mid;

		else	r = mid;

	}

	printf("%.6f\n", mid);

	return 0;

}