CF-1573C Book 题解

题目大意

一本书有n个章节，对于每个章节都有0~k个前置章节，对于每一次阅读，你只能从1看到n，问能否看完，以及看完的最小次数。

解题思路

一开始发现是拓扑排序之后，先用的优先队列。

然后一直wa，以为是写假了。

后面看了下题解，发现用的dp维护。

dp的写完之后，发现有用优先队列过了的。

找了半天bug，发现是优先队列没有重载排序方式。

重载之后就过了。

dp的方法是用dp[i]来表示到达第i个章节至少需要的次数。

对于每个i，枚举他的所有父节点，取父节点的dp最大值maxn，以及最大值时最大的章节数pos。

如果这个点比pos大，dp[i] = maxn，否则，dp[i] = maxn+1。

优先队列的方法类似，把拓扑排序的队列换成优先队列，加一个临时的优先队列tmp。

如果枚举到的这个点需要入队，判断这个点与现在从队列里面拿出来的那个点进行判断。

如果这个点大就可以入队，算成一次阅读。

否则放入tmp。

当q为空的时候，次数加一，判断tmp是否为空，为空则结束，否则把tmp赋给q，tmp清空。

完整代码

dp

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define endl '\n'
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5 + 5;
vector<int> v[N], fa[N];
queue<int> q;
int in[N], dp[N];


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		rep(i, 1, n) {
			int k; cin >> k;
			in[i] = 0, dp[i] = 1;
			if (!k)	q.push(i);
			else {
				in[i] = k;
				while (k--) {
					int x; cin >> x;
					v[x].push_back(i);
					fa[i].push_back(x);
				}
			}
		}
		int ans = 1, cnt = 0;
		while (!q.empty()) {
			int node = q.front(); q.pop();
			cnt++;
			for (auto x : v[node]) {
				in[x]--;
				if (!in[x]) {
					int pos, maxn;
					pos = maxn = -1e9;
					for (auto f : fa[x]) {
						if (dp[f] > maxn) {
							pos = f;
							maxn = dp[f];
						}
						if (dp[f] == maxn)	pos = max(pos, f);
					}
					if (x > pos) dp[x] = maxn;
					else dp[x] = maxn + 1;
					ans = max(ans, dp[x]);
					q.push(x);
				}
			}
		}
		if (cnt == n) 	cout << ans << endl;
		else cout << -1 << endl;
		rep(i, 1, n) v[i].clear(), fa[i].clear();
	}
	return 0;
}

优先队列

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define endl '\n'
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5 + 5;
vector<int> v[N];
queue<int> p;
int in[N];
priority_queue<int,vector<int>,greater<int>> q, tmp;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		rep(i, 1, n) {
			int k; cin >> k;
			in[i] = k;
			if (!k)	q.push(i);
			else {
				while (k--) {
					int x; cin >> x;
					v[x].push_back(i);
				}
			}
		}
		int c = 0, f = 1e9;
		while (!q.empty()) {
			int node = q.top(); q.pop();
			p.push(node);
			for (auto x : v[node]) {
				in[x]--;
				if (!in[x]) {
					if (x > node) q.push(x);
					else tmp.push(x);
				}
			}
			if (q.empty()) {
				c++;
				if (!tmp.empty()) {
					q = tmp;
					while (!tmp.empty()) {
						tmp.pop();
					}
				}
			}
		}
		if (p.size() == n) 	cout << c << endl;
		else cout << -1 << endl;
		rep(i, 1, n) v[i].clear();
		while (!p.empty()) p.pop();
	}
	return 0;
}