P6054 [RC-02] 开门大吉 题解

· · 题解

首先我们可以简单求出第 i 个人做第 j 套题的期望收益 v_{i,j}。

如果没有约束条件，我们就可以贪心的对每个人选择期望收益最小的套题。

而为了将约束条件加进去，我们考虑使用网络流描述上面的贪心做法（本题使用 \lang x,y,w\rang 表示一条 x 到 y 的流量限制为 w 的有向边）：

这样建图后我们跑最小割，不难发现每条链都会割掉恰好一条边，且正好对应着那个人选的那套题。

那么怎么表示约束呢？我们假设存在一个约束 (i,j,k)，那么这相当于是在说：如果第 j 个人选的套题编号 \ge d，那么第 i 个人选的套题编号就必须 \ge d+k。考虑连边 \lang(j,d),(i,d+k),\infty\rang，如果我们在第 j 条链中选择割边 \lang(j,d),(j,d+1)\rang 或更加后面的割边，那么就存在两条从源点到汇点的路径 S\to(i,1)\to(i,2)\to\cdots\to(i,m+1)\to T 和 S\to(j,1)\to(j,2)\to\cdots\to(j,d)\to(i,d+k)\to(i,d+k+1)\to\cdots\to(i,m+1)\to T，为了在第 i 条链中只割掉一条边使这两条路径都被割掉，我们就必须在 (i,d+k)\to(i,d+k+1)\to\cdots\to(i,m+1)\to T 这条路径中选择一条边割掉，于是便限制了 第 i 个人选的套题编号必须 \ge d+k。于是我们就有这样的建图方法：

注意到两组限制 (i,j,k) 与 (u,i,w) 可以推出新的限制 (u,j,k+w)，而在上面的建边中我们也正好可以通过 \lang (j,d),(i,d+k),\infty\rang 和 \lang (i,d+k),(u,d+k+w),\infty\rang 得到边 \lang (j,d),(u,d+k+w),\infty\rang……吗？

注意到如果 k+w\ge m 但 k<m,w<m，限制 (u,j,k+w) 实际上不可能被满足，所以此时无解。但在网络流建模中，因为不存在 d 使得 d+k\le m-w，所以边 \lang (i,d+k),(u,d+k+w),\infty\rang 根本不会被建出，导致限制无法正确传递，从而忽略限制 (u,j,k+w)。

解决这个问题的方法有许多种，这里给出最简单的一种方式：我们去掉 d\le m+1-k 的限制，而在连边时将 d+k 和 m+1 取 \min 即可（即，对一个限制 (i,j,k)，对所有 1\le d\le m+1，连边 \lang(j,d),(i,\min(m+1,d+k)),\infty\rang）。这样我们就可以正确传递限制了。

最后跑一遍最小割即可求出答案。

#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

const int kN = 82, kY = 1e3 + 1;
const double kEps = 1e-6, kI = 1e9;

struct E {
  int y;
  double w;
} e[kN * (kY + kN) * 2];
int tt, n, m, pc, cc, ca[kN];
double pa[kN], va[kN][kN], ans;
int sp, ep, np, ne, d[kN * kN];
vector<int> ed[kN * kN];
vector<int>::iterator it[kN * kN];
int q[kN * kN], qh, qt;

int E(int i, int j) {
  return (i - 1) * (m + 1) + j;
}
void _A(int x, int y, double w) {
  e[++ne] = {y, w};
  ed[x].push_back(ne);
}
void A(int x, int y, double w) {
  _A(x, y, w), _A(y, x, 0);
}
void R(int x, int _d) {
  if (!d[x]) {
    d[x] = _d, q[++qt] = x;
  }
}
bool B() {
  qh = 1, qt = 0;
  fill_n(d + 1, np, 0);
  for (R(sp, 1); qh <= qt; ++qh) {
    int x = q[qh];
    if (x == ep) {
      return 1;
    }
    for (int i : ed[x]) {
      if (e[i].w > kEps) {
        R(e[i].y, d[x] + 1);
      }
    }
  }
  return d[ep];
}
double D(int x, double f) {
  if (f < kEps) {
    return 0;
  }
  if (x == ep) {
    return f;
  }
  double rf = 0;
  for (auto &i = it[x]; i != ed[x].end(); ++i) {
    double iv = 0;
    if (d[e[*i].y] == d[x] + 1 && (iv = D(e[*i].y, min(f - rf, e[*i].w))) > kEps) {
      rf += iv, e[*i].w -= iv, e[*i ^ 1].w += iv;
      if (abs(rf - f) < kEps) {
        break;
      }
    }
  }
  return rf;
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  for (cin >> tt; tt--;) {
    cin >> n >> m >> pc >> cc;
    for (int i = 1; i <= pc; ++i) {
      cin >> ca[i];
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        for (int k = 1; k <= pc; ++k) {
          cin >> pa[k];
        }
        va[j][i] = 0;
        double p = 1;
        int s = 0;
        for (int k = 1; k <= pc; ++k) {
          p *= pa[k], s += ca[k];
          va[j][i] += p * (1 - pa[k + 1]) * s;
        }
      }
    }
    sp = n * (m + 1) + 1, np = ep = n * (m + 1) + 2;
    ne = 1;
    for (int i = 1; i <= np; ++i) {
      ed[i].clear();
    }
    for (int i = 1; i <= n; ++i) {
      A(sp, E(i, 1), kI);
      for (int j = 1; j <= m; ++j) {
        A(E(i, j), E(i, j + 1), va[i][j]);
      }
      A(E(i, m + 1), ep, kI);
    }
    for (int i, j, k; cc--;) {
      cin >> i >> j >> k;
      for (int d = max(1, 1 - k); d <= m + 1; ++d) {
        A(E(j, d), E(i, min(m + 1, d + k)), kI);
      }
    }
    ans = 0;
    for (; B();) {
      for (int i = 1; i <= np; ++i) {
        it[i] = ed[i].begin();
      }
      ans += D(sp, kI);
    }
    if (ans >= kI) {
      cout << "-1\n";
    } else {
      cout << fixed << setprecision(4) << ans << '\n';
    }
  }
  return 0;
}