CF1765H Hospital Queue

题意

给定一张有向无环图，一个合法方案定以为每个点拓扑序满足对应限制，求每个点所有合法方案中的最小拓扑序。

\(1 \leq n, m \le 2000\) ，数据保证存在合法方案。

solution:

对拓扑序的字典序的限制可以用优先队列维护，这道题也可以直接开桶。倒着考虑每个时刻能让那些点成为答案，当答案候选序列为空，这个时候就只能选 i ，总之就是尽量把当前枚举的 i 往后放。只有时刻不大于一个位置的限制时，把这个点加入答案的候选序列。

#include <bits/stdc++.h>
using i64 = long long;
#define fi first
#define se second
int n, m, a[2005], deg[2005];
std::vector<int> g[2005], buc[2005];
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin >> n >> m;
	for (int i = 1; i <= n; ++i) std::cin >> a[i];
	for (int i = 1; i <= m; ++i) {
		int x, y;
		std::cin >> x >> y;
		g[y].emplace_back(x);
	}
	for (int s = 1; s <= n; ++s) {
		memset(deg, 0, sizeof(deg));
		for (int i = 1; i <= n; ++i) {
			for (int v : g[i]) deg[v]++;
		}
		for (int i = 1; i <= n; ++i) buc[i].clear();
		std::vector<int> vec;
		for (int i = 1; i <= n; ++i) {
			if (!deg[i] && i != s) buc[a[i]].push_back(i);
		}
		for (int tim = n; tim; --tim)  {
			for (int x : buc[tim]) vec.push_back(x);
			if (vec.empty()) {
				std::cout << tim << ' ';
				break;
			}
			int u = vec.back();
			vec.pop_back();
			for (int v : g[u]) {
				if (!--deg[v] && v != s) {
					if (a[v] >= tim) vec.push_back(v);
					else buc[a[v]].push_back(v);
				}
			}
		}
	}
	return 0;
}