自动搬运

查看原文

来自洛谷，原作者为

	Left_i_Forever Wish upon a satellite...

搬运于2025-08-24 22:08:04，当前版本为作者最后更新于2025-08-19 16:25:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\Large{\text{Solution}}$

模拟赛时看第三个样例（和本题一样）想到的，比较神秘……

从一个点往回走走到头，可能会有很多个结束的点。反过来，这些点都是拓扑的起点（入度为 $0$），并且都能走到这个点。例如第三个样例中的点都会走到 $1$ 这个点。

令第 $i$ 个点往回走到的终点的集合为 $s_i$，那么 $s_i$ 中必然有至少一个点是发生了的。由于没有其他条件，所以我们无法确定具体是谁发生了，但是可以推理。

对于每一个发生了的 $i$，枚举所有 $j$，若 $s_i$ 是 $s_j$ 的子集，那么 $j$ 一定发生了。注意到只有 $10^3$ 个点，所以 $\Omicron(n^2)$ 是可以接受的。

预处理 $s$ 可以在拓扑排序的时候使用 bitset 优化 DP。

$\Large{\text{Code}}$

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

const int N = 1010;
bitset <N> b[N];
vector <int> v[N], v2[N];
int in[N];
int n, m, d;
bool ans[N];

void topsort()
{
	queue <int> q;
	for (int i = 1; i <= n; i++)
		if (!in[i]) b[i][i] = true, q.push (i);
	while (q.size ())
	{
		int u = q.front ();
		q.pop ();
		for (int j : v[u])
		{
			in[j]--;
			if (!in[j]) q.push (j);
			b[j] |= b[u];
		}
	}
}

int main()
{
//	freopen ("detect.in", "r", stdin);
//	freopen ("detect.out", "w", stdout);
	cin >> n >> m >> d;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		v[x].push_back (y);
		v2[y].push_back (x);
		in[y]++;
	}
	topsort ();
	for (int i = 1; i <= d; i++)
	{
		int x;
		cin >> x;
		for (int j = 1; j <= n; j++)
		{
			bitset <N> tep = b[x] & b[j];
			if (tep == b[x]) ans[j] = true;
		}
	}
	for (int i = 1; i <= n; i++)
		if (ans[i]) cout << i << " ";
	puts ("");
	return 0;
}