[lg3705][SDOI2017]新生舞会

题目大意:

$ n $个男的和女的,每对异性间有两个属性值$ A_{ij} , B_{ij} $。异性两两配对,求$ C = \frac{\sum{A}}{\sum{B}}$的最大值。

设$ \sum {A} = a,\sum {B} = b \ge 0 ,F(C) = a - b C $。

所以将$ F(C) $看作一条直线,则与x轴、y轴正半轴交于两点。

$ x = C_0 $时若$ max(F(C_0)) \lt 0$ 则直线零点在左,否则在右。

于是二分$ C $,求$ F(C) $最大值。

可以费用流,一对间用$ A - BC $做花费(不是$ a - bC$)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <utility>
#include <cmath>
typedef std::pair<double,double> pr;
const int K = 101,N = 2 * K + 2,M = 100010,inf = 0x3f3f3f3f;
const double eps = 1e-7;
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
struct MCMF
{
#define _(a,b) memset(a,b,sizeof(a))
int head[N],pre[N],last[N],vis[N],next[M],to[M];double sflow[N],cap[M],flow[M],cost[M];int s,t,tot;double dis[N];double mxf,mnc;std::queue<int> Q;
MCMF(int s,int t){this->s = s;this->t = t;init();}inline void init(){_(head,-1);for(int i = 0;i < M;i++) flow[i] = 0.0;tot = -1;mxf = mnc = 0.0;}
inline void addedge(int u,int v,double w,double c){next[++tot] = head[u];to[tot] = v;cap[tot] = w;cost[tot] = c;head[u] = tot;}
inline void adde(int u,int v,double w,double c){addedge(u,v,w,c);addedge(v,u,0,-c);}
inline int bfs()
{
_(vis,0);for(int i = 0;i < N;i++) sflow[i] = dis[i] = 1e9;
dis[s] = 0.0;pre[t] = -1;vis[s] = 1;Q.push(s);
while(!Q.empty())
{
int u = Q.front();Q.pop();vis[u] = 0;
for(register int i = head[u],v = to[i];~i;v = to[i = next[i]]) if(cap[i] > flow[i] + eps && dis[v] > dis[u] + cost[i] + eps)
{
dis[v] = dis[u] + cost[i];pre[v] = u;last[v] = i;
sflow[v] = std::min(sflow[u],cap[i] - flow[i]);
if(!vis[v]) {vis[v] = 1;Q.push(v);}
}
}
return ~pre[t] ? 1 : 0;
}
inline pr mcmf()
{
while(bfs())
{
mxf += sflow[t];mnc += sflow[t] * dis[t];
int u = t;while(u != s)
{
flow[last[u]] += sflow[t];flow[last[u] ^ 1] -= sflow[t];
u = pre[u];
}
}
return std::make_pair(mxf,mnc);
}
}D(0,202);
int a[K][K],b[K][K];int s = 0,t = 202;int n;
inline void build(double u)
{
D.init();
for(int i = 1;i <= n;i++) D.adde(s,i,1,0);
for(int i = 1;i <= n;i++) D.adde(i + n,t,1,0);
for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) D.adde(i,j + n,1,-(1.0 * a[i][j] - u * b[i][j]));
}
int main()
{
n = getint();
for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) a[i][j] = getint();
for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) b[i][j] = getint();
double L = 1,R = 200000.0,U,F;
while(1)
{
U = (L + R) / 2;
build(U);
F = -D.mcmf().second;
if(std::fabs(F) <= eps) break;
else if(F < 0) R = U;
else L = U;
}
printf("%.6lf\n",U);
return 0;
}