https://www.luogu.com.cn/problem/P6054
题意概述
有 \(n\) 位选手参与答题，共有 \(m\) 套题，每套包含 \(p\) 道题。
第 \(i\) 位选手答对第 \(j\) 套题的第 \(k\) 道题的概率为 \(f_{i,j,k}\) 。
选手必须按顺序答题，答对获取 \(c_k\) 元，答错直接结束。
存在 \(y\) 条约束关系，每条约束包含三个参数 \(i,j,k\)，表示“第 \(i\) 位选手分配的套题编号必须比第 \(j\) 位选手大 \(k\)” 。
给每位选手分配一套题，求出所有人获得期望奖励之和的最小值，若无法分配，输出 \(-1\) 。
思路
首先计算出第 \(i\) 个人做第 \(j\) 套题的期望奖励 \(a_{i,j}\)。
约束条件比较复杂且数据范围较小，考虑网络流。
对于第 \(i\) 个人的第 \(j\) 套题，连 \((i,j)\) -> \((i,j+1)\)，容量为 \(a_{i,j}\) 的边；同时连 \(s\) -> \((i,1)\)，和 \((i,m+1)\) -> \(t\)，容量均为无穷大的边。
这样割掉 \((i,j)\) -> \((i,j+1)\) 的边就代表第 \(i\) 个人选第 \(j\) 套题。
对于 \(y\) 条约束，可以对所有满足条件的 \(x\)，连 \((j,x)\) -> \((i,min(m+1,x+k))\)，容量为无穷大的边。
可以这样理解：
假如第 \(j\) 个人选了第 \(x\) 套题，那么 \((j,x)\) 属于 \(S\) 集；同时第 \(i\) 个人选了第 \(x'\) 套题， \((j,x')\) 属于 \(S\) 集，那么所有 \(x'' \gt x'\)，\((j,x'')\) 都属于 \(T\) 集。
要求 \(x' \ge x+k\)，那么所有 \(x'' \le x+k\)，\((i,x'')\) 都必须属于 \(S\) 集，为了保证连通性，连 \((j,x)\) 到 \((i,x+k)\) 的边，容量为无穷大保证不会被割掉。
然后跑网络流即可。
代码
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;const ll INF = 1e18;
const double eps = 1e-9;class E{
public:double w;int rev,v;E() = default;E(double w,int rev,int v):w(w),rev(rev),v(v){}
};void solve(){int n,m,p,y;cin >> n >> m >> p >> y;vector<ll> c(p+1);for (int i=1;i<=p;i++){cin >> c[i];} vector<vector<vector<double>>> f(n+1,vector<vector<double>>(m+1,vector<double>(p+1)));for (int j=1;j<=m;j++){for (int i=1;i<=n;i++){for (int k=1;k<=p;k++){cin >> f[i][j][k];}}}vector<array<int,3>> b(y+1);for (int i=1;i<=y;i++){cin >> b[i][0] >> b[i][1] >> b[i][2];}vector<vector<double>> a(n+1,vector<double>(m+1));for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){double res = 0;ll sum = 0;double pe = 1;for (int k=1;k<=p;k++){res += sum*pe*(1-f[i][j][k]);sum += c[k];pe *= f[i][j][k];}res += sum*pe;a[i][j] = res;}}int N = n*(m+1)+2;vector<vector<E>> adj(N+1);int s = N-1;int t = N;auto add = [&](int u,int v,double w){adj[u].push_back({w,(int)adj[v].size(),v});adj[v].push_back({0,(int)adj[u].size()-1,u});};for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){add((i-1)*(m+1)+j,(i-1)*(m+1)+j+1,a[i][j]);}add(s,(i-1)*(m+1)+1,INF);add((i-1)*(m+1)+m+1,t,INF);}for (int tt=1;tt<=y;tt++){auto& [i,j,k] = b[tt];for (int x=1;x<=m;x++){if (x+k<1) continue;add((j-1)*(m+1)+x,(i-1)*(m+1)+min(m+1,x+k),INF); }}vector<int> depth(N+1),cur(N+1);auto bfs = [&](){for (int i=1;i<=N;i++){depth[i] = -1;}depth[s] = 0;queue<int> q;q.push(s);while (!q.empty()){int u = q.front();q.pop();for (auto& [w,rev,v]:adj[u]){if (w>eps && depth[v]==-1){depth[v] = depth[u]+1;q.push(v);if (v==t) return true;}}}return false;};function<double(int,double)> dfs = [&](int u,double mf){if (u==t) return mf;int len = adj[u].size();double sum = 0;for (int& i=cur[u];i<len;i++){auto& [w,rev,v] = adj[u][i];if (w<=eps || depth[v]!=depth[u]+1) continue;double f = dfs(v,min(mf,w));w -= f;mf -= f;adj[v][rev].w += f;sum += f;if (mf<=eps) break;}if (sum<=eps){depth[u] = -1;}return sum;};double mxf = 0;while (bfs()){for (int i=1;i<=N;i++){cur[i] = 0;} mxf += dfs(s,INF);}if (mxf-INF/2>=-eps){cout << -1 << '\n';} else{cout << fixed << setprecision(12) << mxf << '\n';}
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--) solve();return 0;
}