Description

學(xué)校組織了一次新生舞會，Cathy作為經(jīng)驗豐富的老學(xué)姐，負(fù)責(zé)為同學(xué)們安排舞伴。

有 \(n\) 個男生和 \(n\) 個女生參加舞會買一個男生和一個女生一起跳舞，互為舞伴。

Cathy收集了這些同學(xué)之間的關(guān)系，比如兩個人之前認(rèn)識沒計算得出 \(a_{i,j}\)。

Cathy還需要考慮兩個人一起跳舞是否方便，比如身高體重差別會不會太大，計算得出 \(b_{i,j}\)，表示第 \(i\) 個男生和第 \(j\) 個女生一起跳舞時的不協(xié)調(diào)程度。

當(dāng)然，還需要考慮很多其他問題。

Cathy想先用一個程序通過 \(a_{i,j}\) 和 \(b_{i,j}\) 求出一種方案，再手動對方案進行微調(diào)。

Cathy找到你，希望你幫她寫那個程序。

一個方案中有n對舞伴，假設(shè)沒對舞伴的喜悅程度分別是 \(a'_1,a'_2,...,a'_n\)，假設(shè)每對舞伴的不協(xié)調(diào)程度分別是 \(b'_1,b'_2,...,b'_n\)。令

\[ C=\frac{a'_1+a'_2+...+a'_n}{b'_1+b'_2+...+b'_n} \]

Cathy希望 \(C\) 值最大。

Input

第一行一個整數(shù) \(n\)。

接下來 \(n\) 行，每行 \(n\) 個整數(shù)，第 \(i\) 行第 \(j\) 個數(shù)表示 \(a_{i,j}\)。

接下來 \(n\) 行，每行 \(n\) 個整數(shù)，第 \(i\) 行第 \(j\) 個數(shù)表示 \(b_{i,j}\)。

Output

一行一個數(shù)，表示 \(C\) 的最大值。四舍五入保留 \(6\) 位小數(shù)，選手輸出的小數(shù)需要與標(biāo)準(zhǔn)輸出相等。

Sample Input

3 19 17 16 25 24 23 35 36 31 9 5 6 3 4 2 7 8 9

Sample Output

5.357143

HINT

對于10%的數(shù)據(jù)，\(1\le n\le 5\)
對于40%的數(shù)據(jù)，\(1\le n\le 18\)
另有20%的數(shù)據(jù)，\(b_{i,j}\le 1\)
對于100%的數(shù)據(jù)，\(1\le n\le 100,1\le a_{i,j},b_{i,j}<=10^4\)

Solution

分?jǐn)?shù)規(guī)劃，二分答案 \(mid\)，將邊的費用設(shè)為 \(b_{i,j}\cdot mid-a_{i,j}\)，若最小費用 \(>0\)，則令 \(r=mid\)，否則令 \(l=mid\)。

注意 \(1e9+1e^{-8}\) 會爆 \(double\) 的精度，所以避免寫 \(\inf+eps\)。

Code

#include <queue> #include <cstdio> #include <algorithm>const double eps = 1e-8, INF = 1e8; int n, a[102][102], b[102][102], head[205], tot = 1, S, T, p[205], c[205]; double d[205];struct Edge {int u, v, nxt, f, c; double w; Edge(){}Edge(int u, int v, int nxt, int f, int c, double w) : u(u), v(v), nxt(nxt), f(f), c(c), w(w) {} } e[20402];int read() {int x = 0; char c = getchar();while (c < '0' || c > '9') c = getchar();while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();return x; } void adde(int u, int v) {e[++tot] = Edge(u, v, head[u], 0, 1, 0), head[u] = tot;e[++tot] = Edge(v, u, head[v], 0, 0, 0), head[v] = tot; } bool spfa(int &flow, double &cost) {int inq[205] = {}, u; std::queue<int> q;for (int i = 1; i <= T; ++i) d[i] = INF;d[S] = p[S] = 0, q.push(S), inq[S] = 1, c[S] = INF;while (!q.empty()) {u = q.front(), q.pop(), inq[u] = 0;for (int i = head[u]; i; i = e[i].nxt)if (e[i].c > e[i].f && d[e[i].v] > d[u] + e[i].w + eps) {d[e[i].v] = d[u] + e[i].w, p[e[i].v] = i, c[e[i].v] = std::min(c[u], e[i].c - e[i].f);if (!inq[e[i].v]) q.push(e[i].v), inq[e[i].v] = 1;}}if (d[T] + 1 > INF) return false;flow += c[T], cost += c[T] * d[T], u = T;while (u != S) e[p[u]].f += c[T], e[p[u] ^ 1].f -= c[T], u = e[p[u]].u;return true; } double mcmf() {int flow = 0; double cost = 0;while (spfa(flow, cost)) {}return cost; } int main() {n = read(), S = n << 1 | 1, T = S + 1;for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j) a[i][j] = read();for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j) b[i][j] = read();for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j) adde(i, n + j);for (int i = 1; i <= n; ++i) adde(S, i), adde(n + i, T);double l = 0, r = 10000, mid;while (l + eps < r) {mid = (l + r) / 2;for (int i = 1, k = 0; i <= n; ++i)for (int j = 1; j <= n; ++j) k += 2, e[k].w = mid * b[i][j] - a[i][j], e[k ^ 1].w = a[i][j] - mid * b[i][j];for (int i = 2; i <= tot; ++i) e[i].f = 0;if (mcmf() > eps) r = mid; else l = mid;}printf("%.6lf", l);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/fly-in-milkyway/p/10408624.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ 4819] [SDOI 2017] 新生舞会的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。