Description
学校组织了一次新生舞会，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,…,a’n，假设每对舞伴的不协调程度分别是b’1,b’2,…,b’n。令C=(a’1+a’2+…+a’n)/(b’1+b’2+…+b’n),Cathy希望C值最大。
Solution
01分数规划应该算是个套路了，， 化一下式子：
C∑bi−∑ai=0
C
∑
b
i
−
∑
a
i
=
0
我们二分
C
C
，每次将边权赋成
bi,j×C−ai,jbi,j×C−ai,j，跑带权二分图匹配即可。
智障选手只会费用流不会KM23333
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<
int,
int> PII;
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia
template <
typename T>
inline bool chkmax(T &a, T b) {
return a < b ? a = b,
1 :
0; }
template <
typename T>
inline bool chkmin(T &a, T b) {
return b < a ? a = b,
1 :
0; }
inline int read()
{
register int _, __;
register char c_;
for (_ =
0, __ =
1, c_ = getchar(); c_ <
'0' || c_ >
'9'; c_ = getchar())
if (c_ ==
'-') __ = -
1;
for ( ; c_ >=
'0' && c_ <=
'9'; c_ = getchar()) _ = (_ <<
1) + (_ <<
3) + (c_ ^
48);
return _ * __;
}
const double eps =
1e-7;
inline int dcmp(
double x) {
if (
fabs(x) < eps)
return 0;
return x <
0 ? -
1 :
1;
}
const int maxn =
105, maxv =
205, maxm =
20203;
int n, e, v[maxm], f[maxm], nex[maxm], beg[maxv], vis[maxv], tot, s, t, a[maxn][maxn], b[maxn][maxn];
double w[maxm], Cost, dis[maxv];
inline void add(
int uu,
int vv,
int ff,
double ww,
int ty) {
v[++ e] = vv, f[e] = ff, w[e] = ww, nex[e] = beg[uu], beg[uu] = e;
if (ty) add(vv, uu,
0, -ww,
0);
}
inline bool BFS()
{
static queue<int> q;
For(i,
1, tot) dis[i] = INF, Set(vis,
0);
dis[s] =
0, vis[s] =
1, q.push(s);
while (!q.empty())
{
register int u = q.front(); q.pop(), vis[u] =
0;
for (
register int i = beg[u]; i; i = nex[i])
if (f[i] && chkmin(dis[v[i]], dis[u] + w[i]))
if (!vis[v[i]]) vis[v[i]] =
1, q.push(v[i]);
}
return dcmp(dis[t] - INF);
}
int DFS(
int u,
int flow)
{
vis[u] =
1;
if (u == t)
return flow;
register int res = flow, tmp;
for (
register int i = beg[u]; i; i = nex[i])
if (!vis[v[i]] && f[i] && !dcmp(dis[v[i]] - dis[u] - w[i]))
{
tmp = DFS(v[i], min(f[i], res));
f[i] -= tmp, f[i ^
1] += tmp, Cost += tmp * w[i];
if (!(res -= tmp))
return flow;
}
return flow - res;
}
inline double MCMF()
{
Cost =
0.;
while (BFS())
do Set(vis,
0), DFS(s, n);
while (vis[t]);
return Cost;
}
inline double check(
double c)
{
e =
1, Set(beg,
0);
For(i,
1, n) add(s, i,
1,
0,
1), add(i + n, t,
1,
0,
1);
For(i,
1, n) For(j,
1, n) add(i, j + n,
1, b[i][j] * c - a[i][j],
1);
return MCMF();
}
int main()
{
#ifdef hany01
File(
"bzoj4819");
#endif
static int Min = INF, Max =
0;
n = read();
For(i,
1, n) For(j,
1, n) chkmax(Max, a[i][j] = read());
For(i,
1, n) For(j,
1, n) chkmin(Min, b[i][j] = read());
static double l =
1e-4, r = Max *
1. / Min, mid;
s = n <<
1 |
1, t = tot = (n +
1) <<
1;
while (r - l >= eps) {
mid = (l + r) *
.5;
if (check(mid) <
0) l = mid;
else r = mid;
}
printf(
"%.6lf\n", l);
return 0;
}
