题解：P16072 [ICPC 2023 NAC] Fail Fast

· · 题解

题意简述

有 n 个测试，第 i 个测试耗时 c_i，独立通过的概率为 p_i，至多依赖另一个测试。依赖关系无环，必须先执行被依赖的测试。

遇到第一个失败的测试后停止，费用为已经消耗的时间；若所有测试都通过，费用记为 0。构造一种合法执行顺序，使期望费用最小。

解题思路

暂时将全通过时的费用也设为所有测试耗时之和。对于执行顺序 a_1,a_2,\dots,a_n，此时的期望费用是：

E=\sum_{i=1}^n c_{a_i}\prod_{j=1}^{i-1}p_{a_j}

第 i 个测试会执行，当且仅当前面的测试全部通过。

题目真正的期望费用等于 E 减去「全部通过的概率乘总耗时」。这个被减去的量与执行顺序无关，因此只需最小化 E。

将若干连续执行的测试视为一个块。对于块 A，记 C_A 为进入该块后的期望耗时，P_A 为块内全部测试通过的概率。依次执行 A,B，合并块的两个量为：

\begin{aligned} C_{AB} & =C_A+P_AC_B \\ P_{AB} & =P_AP_B \end{aligned}

比较 AB 与 BA。两种顺序对后续部分的影响相同，因为它们全部通过的概率都是 P_AP_B；此前的通过概率也是相同的公共因子。故 A 放在 B 前面不劣，当且仅当：

C_A(1-P_B)\le C_B(1-P_A)

所有非空块都有 P_A<1，可以按比值 C_A/(1-P_A) 从小到大比较。实现中直接交叉相乘，避免额外除法。

没有依赖时，按上述比值排序即可。有依赖时，不能只在当前可以执行的测试中贪心，因为某个较慢测试可能解锁非常值得提前执行的后继。

加入虚拟测试 0，耗时为 0，通过概率为 1，让所有无依赖测试依赖它。依赖关系变成以 0 为根的树。开始时，每个真实测试单独成为一个块；虚拟测试也单独成块。

在所有不含虚拟测试的当前块中，选比值最小的块 A，设其直接父块为 B。我们将 A 紧接在 B 后面，并把二者收缩成一个新块。

为什么可以强制它们连续？考虑当前块问题的一种最优顺序。父块 B 一定在 A 前面。将 A 向前移动，直到紧挨 B：

所以一定存在一种最优顺序让 BA 连续，收缩不会排除全部最优解。新块的依赖对象仍是原来 B 的父块，其他依赖仍形成树。用合并公式更新后，就得到规模更小的同类问题，可以继续贪心。

反复收缩后只剩包含虚拟测试的一个块，其内部顺序就是所求答案。虚拟块始终在最前面，不参与比值选择，也不输出。

用并查集维护每个原测试当前属于哪个块。head 保存块的第一个测试，tail 保存最后一个测试，nxt 将块内顺序连成链表。把块 A 接到 B 后面只需修改一次链表指针，不必搬移整段测试。

当前块的外部依赖，是 head 对应原测试的依赖对象所在的块。并查集采用按大小合并，代表元不一定是块的第一个测试，所以不能把代表元直接当成 head。合并前先保存顺序信息与新概率、新期望，选好代表元后再一起写回，避免并查集换根改变执行顺序。

最小比值用堆维护。块被吸收，或者合并后数值改变，原堆条目都会失效；用代表元检查和版本号丢弃这些旧条目。每次合并至多插入一个新条目，总插入数为 O(n)。

概率及期望使用 long double。按大小合并也限制了并查集树高，配合路径压缩，避免长依赖链产生深递归。总时间复杂度为 O(n\log n)，空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ld=long double;
const int N=100005;
struct Node
{
    ld c,p;
    int id,ver;
    bool operator<(const Node &x)const
    {
        ld a=c*(1-x.p),b=x.c*(1-p);
        return a!=b?a>b:id>x.id;
    }
};
ld c[N],p[N];
int d[N],fa[N],siz[N],head[N],tail[N],nxt[N],ver[N];
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    p[0]=1;
    siz[0]=1;
    priority_queue<Node> q;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i]>>p[i]>>d[i];
        fa[i]=head[i]=tail[i]=i;
        siz[i]=1;
        q.push({c[i],p[i],i,0});
    }
    for(int i=1;i<=n;i++)
    {
        while(fa[q.top().id]!=q.top().id||ver[q.top().id]!=q.top().ver)q.pop();
        int u=q.top().id;
        q.pop();
        int v=find(d[head[u]]);
        nxt[tail[v]]=head[u];
        ld x=c[v]+p[v]*c[u],y=p[v]*p[u];
        int h=head[v],t=tail[u];
        if(siz[u]>siz[v])swap(u,v);
        fa[u]=v;
        siz[v]+=siz[u];
        c[v]=x;
        p[v]=y;
        head[v]=h;
        tail[v]=t;
        ver[v]++;
        if(h)q.push({c[v],p[v],v,ver[v]});
    }
    for(int i=nxt[0];i;i=nxt[i])cout<<i<<'\n';
    return 0;
}