[SDOI2017新生舞会]分数规划+网络流

考虑二分 $C$ ,判断当前答案 $C$ 是否可行

若 $\frac{a_1’+a_2’+a_3’+\dots}{b_1’+b_2’+b_3’+\dots}>C$ 则说明当前答案 $C$ 可行

移项后原式化为 $a_1’-C\times b_1’+a_2’-C\times b_2’\dots>0$ ,所以只需判断该式是否大于0

可以考虑用最大费用最大流判断答案

  • 由原点对每个男生连一条流量为1费用为0的边
  • 由每个女生对汇点连一条流量为1费用为0的边
  • 由每个女生对每个男生连一条流量为1费用为 $a_{i,j}-C\times b_{i,j}$

最后看一下最大费用是否大于0即可

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/***************************************************************
File name: P3705.cpp
Author: ljfcnyali
Create time: 2019年10月11日 星期五 08时19分36秒
***************************************************************/
#include<bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for ( int i = (a), _end_ = (b); i <= _end_; ++ i )
#define mem(a) memset ( (a), 0, sizeof ( a ) )
#define str(a) strlen ( a )
#define pii pair<int, int>
typedef long long LL;

const int maxn = 100010;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;

int n, a[110][110], b[110][110], ans;

namespace MCMF
{
int Begin[maxn], Next[maxn], To[maxn], From[maxn], e = 1, W[maxn], a[maxn], pre[maxn];
double F[maxn], dis[maxn];
bool vis[maxn];

inline void INIT() { mem(Begin); e = 1; }

inline void add(int u, int v, int w, double f)
{
To[++ e] = v; From[e] = u; Next[e] = Begin[u]; Begin[u] = e; W[e] = w; F[e] = f;
To[++ e] = u; From[e] = v; Next[e] = Begin[v]; Begin[v] = e; W[e] = 0; F[e] = -f;
}

inline bool BFS(int s, int t)
{
REP(i, 1, t) dis[i] = -INF; mem(vis);
dis[s] = 0; a[s] = INF; vis[s] = true;
queue<int> Q; Q.push(s);
while ( !Q.empty() )
{
int u = Q.front(); Q.pop();
for ( int i = Begin[u]; i; i = Next[i] )
{
int v = To[i];
if ( dis[v] < dis[u] + F[i] && W[i] > 0 )
{
dis[v] = dis[u] + F[i];
a[v] = min(a[u], W[i]);
pre[v] = i;
if ( !vis[v] ) { vis[v] = true; Q.push(v); }
}
}
vis[u] = false;
}
if ( dis[t] == -INF ) return false;
return true;
}

inline bool SPFA(int s, int t, int &flow, double &cost)
{
if ( !BFS(s, t) ) return false;
flow += a[t]; cost += a[t] * dis[t];
int u = t;
while ( u != s )
{
W[pre[u]] -= a[t];
W[pre[u] ^ 1] += a[t];
u = From[pre[u]];
}
return true;
}

inline void Solve(int s, int t, int &flow, double &cost)
{
flow = cost = 0;
while ( SPFA(s, t, flow, cost) ) ;
}
}

inline bool Check(double x)
{
MCMF :: INIT();
int s = 0, t = n + n + 1, flow; double cost;
REP(i, 1, n)
{
MCMF :: add(s, i, 1, 0);
MCMF :: add(n + i, t, 1, 0);
}
REP(i, 1, n) REP(j, 1, n) MCMF :: add(i, n + j, 1, a[i][j] - x * b[i][j]);
MCMF :: Solve(s, t, flow, cost);
return cost >= 0;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
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;
REP(i, 1, 100)
{
double Mid = (L + R) / 2;
if ( Check(Mid) ) L = Mid;
else R = Mid;
}
printf("%.6lf\n", L);
return 0;
}