年功序列
题目描述
在虚拟国度里多了很多 Virtual oier，为了树立对后辈的威信，从第 1 1 1 个 Virtual oier 开始的 oier 们搞起了年功序列的制度。
虚拟国度的创始人 oier Chtholly 感觉非常有趣，于是他决定观测 1 1 1 到 n n n 这些人，他观测到了一些有趣的现象：虚拟国度里有一些凳子，如果 a a a 是 b b b 的先辈则 a a a 能在 b b b 前面得到凳子
Chtholly的观测可以构成 m m m 个序列，每个序列有 k k k 个元素 a 1 , a 2 , a 3 , ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ , a k a_{1}, a_{2}, a_{3}, ······, a_{k} a1,a2,a3,⋅⋅⋅⋅⋅⋅,ak。表示在 a i a_{i} ai 有凳子前 a 1 , a 2 , a 3 , ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ , a i − 1 a_{1}, a_{2}, a_{3}, ······, a_{i - 1} a1,a2,a3,⋅⋅⋅⋅⋅⋅,ai−1 必须有凳子。( a i − 1 a_{i - 1} ai−1 是 a i a_{i} ai 的前辈)
例如 k = 3 k = 3 k=3 时： a = 1 ， 2 ， 3 a = 1，2，3 a=1，2，3，表示 3 3 3 有凳子前 1 , 2 1, 2 1,2必须都有凳子， 2 2 2 有凳子前 1 1 1 必须有凳子。
但 Chtholly 年纪大了记忆力未必好，如果第 i i i 个序列与前 i − 1 i - 1 i−1 个序列冲突的话那么就只需要考虑前 i − 1 i - 1 i−1 个序列就好了。(忽略第 i i i 个序列)
Chtholly 希望知道 1 1 1 到 n n n 个人的年功序列的最小字典序。
输入格式
第一行两个数 n , m n, m n,m
接下来 m 行每行第一个数为 k k k，接下来 k k k 个数为这次观测构成的序列
输出格式
输出 n n n 个数构成的最小字典序。
样例
样例输入
4 3
3 1 2 3
2 4 2
3 3 4 1样例输出
1 4 2 3
样例解释
第三个观测序列与前两个观测序列冲突不考虑，前两个观测序列可以构成 1 1 1 4 4 4 2 2 2 3 3 3 或者 4 4 4 1 1 1 2 2 2 3 3 3 这两个序列，字典序小的为 1 1 1 4 4 4 2 2 2 3 3 3。
数据范围与提示
30 30 30%的数据， n ≤ 10 , m ≤ 4 n \leq 10, m \leq 4 n≤10,m≤4
50 50 50%的数据， n ≤ 10000 , m ≤ 5000 n \leq 10000, m \leq 5000 n≤10000,m≤5000
100 100 100%的数据， n ≤ , m ≤ 50000 , k ≤ n n \leq , m \leq 50000, k \leq n n≤,m≤50000,k≤n
分析
这道题看似很难、很复杂，其实是道简单的拓扑排序。
我们可以把 a [ 1 ] a[1] a[1] ~ a [ i − 1 ] a[i - 1] a[i−1] 看成 a [ i ] a[i] a[i] 的入度。(下面也这样说明)
但是我们只需要把 a [ i − 1 ] a[i - 1] a[i−1] 看成 a [ i ] a[i] a[i] 的入度即可。 ( ( ( 因为我们求到 a [ i − 1 ] a[i - 1] a[i−1] 的时候，前面的 a [ 1 ] a[1] a[1] ~ a [ i − 2 ] a[i - 2] a[i−2] 一定是求过的 ( ( ( 不然不会求到 a [ i − 1 ] a[i - 1] a[i−1] 的 ) ) ) ) ) )
——但是这道题的难点在于冲突的情况
思路
我们先输入第 i i i 组的数据 ，把 这组数据 及 以前的数据(没有舍弃的数据) 进行拓扑排序，再判断是否出现了环：
- 如果出现了，就把 这组数据舍弃 (同时也要把 新加进来的 入度 和 每个点的入度个数 还原)。
代码
正解代码如下：
#include <cstdio> #include <cstring> #include <queue> #include <vector> using namespace std; const int MAXN = 1e5 + 5; int N, M, K; int num[MAXN]; vector<int> ans, E[MAXN]; int in[MAXN]; // 每个人的前辈个数 bool vis[MAXN]; struct node {
int numn; node(){
} node (int n) {
numn = n; } friend bool operator < (node a, node b) {
return a.numn > b.numn; } // 字典序排序 }; void toposort() // 拓扑排序 {
priority_queue<node> q; for (int i = 1; i <= N; i++) if (in[i] == 0) q.push(node(i)); // 不一定每个人都有前辈, 所以不需要判断每个人是否被输入 while (!q.empty()) {
int u = q.top().numn; q.pop(); ans.push_back(u); int siz = E[u].size(); for (int i = 0; i < siz; i++) {
int v = E[u][i]; --in[v]; if (in[v] == 0) q.push(node(v)); } } } bool check(int u) // 判断是否产生环 {
int siz = E[u].size(); for (int i = 0; i < siz; i++) {
int v = E[u][i]; if (vis[v]) return 0; vis[v] = 1; if (!check(v)) return 0; } vis[u] = 0; return 1; } int main() {
scanf("%d %d", &N, &M); for (int i = 1; i <= M; i++) {
scanf("%d", &K); for (int j = 1; j <= K; j++) {
scanf("%d", &num[j]); if (j == 1) continue; // 第1个人没有前辈 E[num[j - 1]].push_back(num[j]), ++in[num[j]]; } memset(vis, 0, sizeof(vis)); vis[num[1]] = 1; if (!check(num[1])) // 为什么从第1人开始判断, 就留给读者自己思考了 {
// 还原 for (int j = 2; j <= K; j++) {
// 删除这个入度 --in[num[j]]; E[num[j - 1]].pop_back(); } break; } } toposort(); int siz = ans.size(); for (int i = 0; i < siz; i++) printf("%d ", ans[i]); return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/65994.html