2019湖南省赛G 字典序（建图，拓扑排序）

本文主要是介绍2019湖南省赛G 字典序（建图，拓扑排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：
之前听学长讲的思路是用$bitset$优化暴力写，对于每一行的大小关系依次确定（第$i$行大于第$i-1$行）。
也就是对于已经选择的列，确定了前$i$行大小关系了，那就继续遍历剩下的列，使得能确定第$i+1$行关系（或者更多），前提是不会破坏后面的大小关系。用$bitset$优化这个过程以后复杂度是$O(\frac{n^3}{64})$，lh现场赛还真乱搞过了XD。

$n^2$写法与暴力写法类似，也是要按照行依次确定大小关系。

• 对于第$j$列，如果$a[i][j]>a[i][j-1]$，这就意味着选择第$j$列，我们可以确定第$i$行的大小关系；
• 如果$a[i][j]<a[i][j-1]$，这就意味着要选择第$j$列的前提是确定了第$i$行的大小关系。
• 这里就有一个前驱的关系，我们以此建图跑跑拓扑排序就是一个可行解。
• 本题要求字典序最小，所以使用优先队列，保证每次选择当前序号最小的可行列。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 2e3 + 7;
int n,m;
int a[maxn][maxn],deg[maxn];
bool vis[maxn];
priority_queue<int,vector<int>,greater<int>>q;
vector<int>N[maxn],M[maxn];
vector<int>ans;void init() {ans.clear();while(!q.empty()) q.pop();for(int i = 1;i <= n;i++) {N[i].clear();vis[i] = 0;}for(int i = 1;i <= m;i++) {M[i].clear();deg[i] = 0;}for(int i = 1;i <= n;i++) {for(int j = 1;j <= m;j++) {scanf("%d",&a[i][j]);}}for(int i = 2;i <= n;i++) {for(int j = 1; j<= m;j++) {if(a[i][j] > a[i - 1][j]) { //这一列能确定的行关系M[j].push_back(i);}if(a[i][j] < a[i - 1][j]) { //要选择第j列，要提前确定第i行关系N[i].push_back(j);deg[j]++;}}}
}void topo() {for(int i = 1;i <= m;i++) { //哪些列没有被其他列限制，直接放在如队if(deg[i] == 0) {q.push(i);}}while(!q.empty()) {int now = q.top();q.pop();ans.push_back(now);//选择这一列for(int i = 0;i < M[now].size();i++) { //遍历这一列能确定的行关系int v = M[now][i];if(vis[v]) continue;//确定过的行关系就不再用了vis[v] = true;for(int j = 0;j < N[v].size();j++) { //减掉这个行关系所限制的列int w = N[v][j];deg[w]--;if(deg[w] == 0) {q.push(w);}}}}
}void Print() {if(ans.size() != m) {printf("-1\n");return;}for(int i = 0;i < ans.size();i++) {printf("%d",ans[i]);if(i == ans.size() - 1) printf("\n");else printf(" ");}
}int main() {while(~scanf("%d%d",&n,&m)) {init();topo();Print();}return 0;
}

这篇关于2019湖南省赛G 字典序（建图，拓扑排序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---