BZOJ 4819新生舞会 _BZOJ

业无高卑志当坚，男儿有求安得闲？这篇文章主要讲述BZOJ 4819新生舞会相关的知识，希望能为你提供帮助。
1.??题目链接??。题意十分的好懂，做法也是十分的裸。
2.把分式变形一下：

这样，把每条边的权值赋值为a[i][j]-C*b[i][j]，显然C是单调的。二分这个C，对于每个C，判断图存不存在一个完美的匹配。注意权值非负。判断是不是完美匹配，费用流或者KM都行。这里采用KM实现

#include< bits/stdc++.h>
#define rep(i,l,r) for (int i=l; i< =r; i++)
#define For(i,x) for (int i=h[x],k; i; i=nxt[i])
using namespace std;

const int N = 210, inf = 1000000000;
const double eps = 1e-10;
int n, lk[N], vx[N], vy[N], a[N][N], b[N][N];
double lx[N], ly[N], w[N][N], s[N];
double ABS(double x)return (x < 0) ? -x : x;
bool dfs(int x)
vx[x] = 1;
rep(y, 1, n) if (!vy[y])
double t = lx[x] + ly[y] - w[x][y];
if (ABS(t) < eps)
vy[y] = 1;
if (lk[y] == -1 || dfs(lk[y]))lk[y] = x; return 1;

else s[y] = min(s[y], t);

return 0;

double KM()
rep(i, 1, n) lx[i] = -inf, ly[i] = 0, lk[i] = -1;
rep(i, 1, n) rep(j, 1, n) lx[i] = max(lx[i], w[i][j]);
rep(x, 1, n)
rep(i, 1, n) s[i] = inf;
while (1)
memset(vx, 0, sizeof(vx));
memset(vy, 0, sizeof(vy));
if (dfs(x)) break;
double d = inf;
rep(i, 1, n) if (!vy[i]) d = min(d, s[i]);
rep(i, 1, n) if (vx[i]) lx[i] -= d;
rep(i, 1, n) if (vy[i]) ly[i] += d; else s[i] -= d;

double res = 0;
rep(i, 1, n) res += w[lk[i]][i];
return res;

int main()
scanf("%d", & n);
rep(i, 1, n) rep(j, 1, n) scanf("%d", & a[i][j]);
rep(i, 1, n) rep(j, 1, n) scanf("%d", & b[i][j]);
double L = 0, R = 10000;
while (L + eps < R)
double mid = (L + R) / 2;
rep(i, 1, n) rep(j, 1, n) w[i][j] = a[i][j] - mid * b[i][j];
if (KM() > eps) L = mid; else R = mid;

printf("%.6lf\\n", L);
return 0;