#include #include #include #include using namespace std; const int MAXN = 2e2 + 5; const int MAXM = 2e4 + 5; const int INF = 0x3f3f3f3f; #define Eps 1e-8 struct Edge { int To, Cap, Next; long double Cost; }; Edge edge[MAXM << 1]; int head[MAXN], tot = 1; void Addedge(int u, int v, int w, long double c) { edge[++tot].Next = head[u], edge[tot].To = v, edge[tot].Cap = w, edge[tot].Cost = c, head[u] = tot; edge[++tot].Next = head[v], edge[tot].To = u, edge[tot].Cap = 0, edge[tot].Cost = -c, head[v] = tot; } priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; long double dis[MAXN], h[MAXN], mcmf; int dep[MAXN], pre[MAXN], lim[MAXN]; bool vis[MAXN]; int a[105][105], b[105][105]; int n, m, s, t; int Min(int x, int y) { return x < y ? x : y; } bool Dijkstra() { for (int i = s; i <= t; i++) vis[i] = 0, pre[i] = 0, lim[i] = dis[i] = INF; dis[s] = 0, pq.push(make_pair(0, s)); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = 1; for (int i = head[u]; i; i = edge[i].Next) { int v = edge[i].To; if (dis[v] > dis[u] + edge[i].Cost + h[u] - h[v] && edge[i].Cap) { pre[v] = i, lim[v] = min(lim[u], edge[i].Cap); dis[v] = dis[u] + edge[i].Cost + h[u] - h[v]; pq.push(make_pair(dis[v], v)); } } } for (int i = s; i <= t; i++) if (dis[i] < INF) h[i] += dis[i]; return dis[t] != INF; } int Update() { int now = t; while (now != s) { int i = pre[now]; edge[i].Cap -= lim[t]; edge[i ^ 1].Cap += lim[t]; mcmf += lim[t] * edge[i].Cost; now = edge[i ^ 1].To; } return lim[t]; } int EK() { int res = 0; while (Dijkstra()) res += Update(); return res; } bool Check(long double mid) { for (int i = s; i <= t; i++) head[i] = 0, h[i] = 0; tot = 1; mcmf = 0; t = 2 * n + 1; for (int i = 1; i <= n; i++) Addedge(s, i, 1, 0); for (int i = 1; i <= n; i++) Addedge(i + n, t, 1, 0); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { Addedge(i, j + n, 1, mid * b[i][j] - a[i][j]); } } EK(); return mcmf <= 0; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &b[i][j]); long double l = 0, r = 1e4; while (r - l >= Eps) { long double mid = (l + r) / 2; }