年功序列c++游戏
题目描述
在虚拟国度里多了很多 Virtual oier，为了树立对后辈的威信，从第 11 个 Virtual oier 开始的 oier 们搞起了年功序列的制度。
虚拟国度的创始人 oier Chtholly 感觉非常有趣，于是他决定观测 11 到 nn 这些人，他观测到了一些有趣的现象：虚拟国度里有一些凳子，如果 aa 是 的先辈则 能在 前面得到凳子
Chtholly的观测可以构成 mm 个序列，每个序列有 kk 个元素 a1,a2,a3,??????,aka1a 2a3,??????,a k。表示在 aia 有凳子前 a1,a2,a3,??????,ai?1a 1a2 ,a 3??????,a i?1必须有凳子。(ai?1a i?1是 aia的前辈)
例如 k = 3 时：a=1，2，3a=1，2，3，表示 33 有凳子前 1,21,2必须都有凳子，22 有凳子前 11 必须有凳子。
但 Chtholly 年纪大了记忆力未必好，如果第 ii 个序列与前 i?1i?1 个序列冲突的话那么就只需要考虑前 i?1i?1 个序列就好了。(忽略第 ii 个序列)
Chtholly 希望知道 11 到 nn 个人的年功序列的最小字典序。
输入格式
第一行两个数 n,mn,m
接下来 m 行每行第一个数为 kk，接下来 kk 个数为这次观测构成的序列
输出格式
输出 nn 个数构成的最小字典序。
样例
样例输入
4 3
3 1 2 3
2 4 2
3 3 4 1
样例输出
1 4 2 3
样例解释
第三个观测序列与前两个观测序列冲突不考虑，前两个观测序列可以构成 11 44 22 33 或者 44 11 22 33 这两个序列，字典序小的为 11 44 22 33。
数据范围与提示
3030%的数据，n≤10,m≤4n≤10,m≤4
5050%的数据，n≤10000,m≤5000n≤10000,m≤5000
100100%的数据，n≤100000,m≤50000,k≤nn≤100000,m≤50000,k≤n
题目分析
首先，如果不考虑有冲突的情况下，那这就是一道模板题了，也就是用优先队列的拓扑排序，于是，问题便变成如何处理冲突
首先有一个思路，就是用dfs,一个一个地添加序列，如果，拓扑排序满足的话，就可以直接输出了，但是，这个思路首先肯定会T，其次，可能不会满足字典序最小，于是，就又要想其他思路了
好好读题，会发现
如果第 i个序列与前 i+1个序列冲突的话那么就只需要考虑前 i个序列就好了。
思考一下，会发现，每一个序列满足必须是前一个序列满足，所以，如果有一个序列不满足，剩余的就不用输入了下一个问题，便成了如何判断可行
这时，回归拓扑排序的定义， 无环 ，也就是判断是否有环
for (int i = 0; i < g[x].size(); i++) //邻接表
{
if (vis[g[x][i]]) //已经走过
{
return 0;
}
vis[g[x][i]] = 1; //标记
if (!check(g[x][i])) //如果下一个顶点有环，说明，这张图都有环
{
return 0;
}
vis[g[x][i]] = 0;//回溯
}
return 1;
}
因为判断要用邻接表，所以，如果判断有环，我们要删去邻接表,顺便，就删去
入度的tot
for(int j=1;j<k;j++) {g[a[j]].pop_back(); tot[a[j+1]]--; }
代码
#include#include #include #include using namespace std; int x, y; int m; int n; int tot[100005]; vector<int> g[100005]; vector<int> ans; int vis[100005]; int k; int cnt = 0; int a[100005]; priority_queue<int, vector<int>, greater<int> > q; bool check(int x) { for (int i = 0; i < g[x].size(); i++) //邻接表 { if (vis[g[x][i]]) //已经走过 { return 0; } vis[g[x][i]] = 1; //标记 if (!check(g[x][i])) //如果下一个顶点有环，说明，这张图都有环 { return 0; } vis[g[x][i]] = 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", &a[j]); if (j == 1) { continue; } // 1没有入度 g[a[j - 1]].push_back(a[j]); tot[a[j]]++; } memset(vis, 0, sizeof(vis)); if (!check(a[1])) { for (int j = 1; j < k; j++) { g[a[j]].pop_back(); tot[a[j + 1]]--; } break; } } for (int i = 1; i <= n; i++) { if (!tot[i]) { q.push(i); } } while (!q.empty()) { int k = q.top(); q.pop(); ans.push_back(k); for (int i = 0; i < g[k].size(); i++) { tot[g[k][i]]--; if (!tot[g[k][i]]) { q.push(g[k][i]); } } } for (int i = 0; i < ans.size(); i++) { printf("%d ", ans[i]); }
}