题解 P3705 【[SDOI2017]新生舞会】

Log_x

2017-05-07 21:28:34

Solution

**费用流+分数规划+二分答案** 首先我们可以想到二分答案C,但C的满足条件似乎并不好处理 但我们可以利用分数规划的思想将C进行转换 ```cpp C = (a1 + a2 + …… + an) / (b1 + b2 + …… + bn) (b1 + b2 + …… + bn) * C = (a1 + a2 + …… + an) (a1 + a2 + …… + an) - (b1 + b2 + …… + bn) * C = 0 (a1 - b1 * C) + (a2 - b2 * C) + …… + (an - bn * C) = 0 ``` 由此我们得出这道二分图的最小费用最大流: 1)将源点向每个男生连一条流量为1、费用为0的边 2)将每个女生向汇点连一条流量为1、费用为0的边 3)将每一对男女舞伴间连一条流量为1、费用为[a[i][j] - b[i][j] \* C]的边 然后每次判断最小费用是否小于(或大于)0来缩小边界,最后得到答案。 **代码如下:** ```cpp #include <iostream> #include <cstdio> #include <cstring> using namespace std; const double Maxn = 1e9; const int N = 205, M = 8e4 + 5; const double eps = 1e-8; int pre[N], nxt[M], to[M], lst[N], fr[M], flw[M], Q[M]; int n, s, t, T; bool vis[N]; double a[N][N], b[N][N], cst[M], Ans, dis[N]; template <class T> inline void CkMin(T &a, const T b) {if (a > b) a = b;} inline void Add(const int x, const int y, const int z, const double g) { nxt[++T] = lst[x]; lst[x] = T; to[T] = y; fr[T] = x; flw[T] = z; cst[T] = g; nxt[++T] = lst[y]; lst[y] = T; to[T] = x; fr[T] = y; flw[T] = 0; cst[T] = -g; } inline bool Bul() { for (int i = s; i <= t; ++i) dis[i] = -Maxn; int te = 0, we = 1, x, y; dis[Q[1] = s] = 0.0; while (te < we) { x = Q[++te]; vis[x] = false; for (int i = lst[x]; i; i = nxt[i]) if (dis[y = to[i]] < dis[x] + cst[i] && flw[i]) { dis[y] = dis[x] + cst[i]; pre[y] = i; if (!vis[y]) vis[y] = true, Q[++we] = y; } } return dis[t] > -Maxn; } inline void Deal() { int Mif = Maxn; for (int i = pre[t]; i; i = pre[fr[i]]) CkMin(Mif, flw[i]); for (int i = pre[t]; i; i = pre[fr[i]]) flw[i] -= Mif, flw[i ^ 1] += Mif, Ans += (double)Mif * cst[i]; } inline bool check(const double mi) { T = 1; memset(lst, 0, sizeof(lst)); for (int i = 1; i <= n; ++i) Add(s, i, 1, 0), Add(i + n, t, 1, 0); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) Add(i, j + n, 1, a[i][j] - mi * b[i][j]); Ans = 0.0; while (Bul()) Deal(); return (Ans <= 0); } int main() { scanf("%d", &n); s = 0; t = (n << 1) + 1; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) scanf("%lf", &a[i][j]); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) scanf("%lf", &b[i][j]); double l = 0, r = 1e4; while (r - l >= eps) { double mid = (l + r) / 2; (check(mid) ? r : l) = mid; } return printf("%.6lf\n", l), 0; } ```