题解：P5954 [JSOI2013] 侦探 JYY

· · 题解

注意到题目中的线索具有传递性，并且整个图是一个 DAG，任意事件不会通过线索导致自身发生。这提示我们可以用拓扑排序来处理事件之间的因果关系。

考虑一个事件在什么情况下必然发生。如果某个已知发生的事件 d，它的所有“源头”也都能导致 v 发生，那么 v 就必然发生。因为 d 的发生意味着它的某个源头发生了，而这个源头同样会导致 v。因此我们只需要关注每个事件能被哪些源头事件到达。

注意到入度为 0 的事件不可能被其他事件导致，它们就是因果链的起点，也就是我们所说的源头。对于每个事件 v，考虑维护 s(v) 表示所有能到达 v 的源头集合。在拓扑排序的过程中，当我们从 u 走到 v 时，将 s(u) 合并到 s(v) 中，这样最终每个点的 s 就包含了所有能导致它发生的源头。

由于 N \leq 1000，考虑用 bitset 来存储源头集合，每次合并是 O( \frac{N}{w}) 的，完全可行。

对于每个已知发生的事件 d，d 的发生意味着 s(d) 中至少有一个源头发生了。现在对于一个待判断的事件 v，如果存在某个已知事件 d，使得 s(d) \subseteq s(v)，即所有能导致 d 的源头也都能导致 v，那么无论 s(d) 中哪个源头发生，都必然会导致 v 发生，因此 v 一定发生了。反之，如果对于每个 d 都有 s(d) \not\subseteq s(v)，那就无法确定 v 一定发生。

综上，我们首先找出所有入度为 0 的源头并编号，通过拓扑排序用 bitset 传递源头信息，最后对每个事件 v 检查是否存在已知事件 d 满足 s(d) 是 s(v) 的子集，即可得到所有必然发生的事件。

拓扑排序配合 bitset 传递源头信息的复杂度为 O(M + \frac{N^2}{w})，最终判断的复杂度为 O(\frac{DN^2}{w})，在 N \leq 1000 时足以通过。

细节详见代码。

#include<bits/stdc++.h>
#define N 1005
#define endl '\n'
using namespace std;

int n,m,d,in[N];
vector<int> e[N],vec,ans;
bitset<N> s[N];

signed main()
{
    scanf("%d%d%d",&n,&m,&d);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        in[v]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(in[i]==0){
            s[i].set(i);
            q.push(i);
        }
    }
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int v:e[u]){
            s[v]|=s[u];
            if(--in[v]==0) q.push(v);
        }
    }
    for(int i=1;i<=d;i++){
        int x;
        scanf("%d",&x);
        vec.push_back(x);
    }
    for(int i=1;i<=n;i++){
        bool f=0;
        for(int tmp:vec){
            if((s[tmp]&~s[i])==0){
                f=1;
                break;
            }
        }
        if(f) ans.push_back(i);
    }
    for(int res:ans){
        printf("%d ",res);
    }
    return 0;
}