分数规划+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
", mid);
return 0;
}