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

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

在这里插入图片描述

思路：
之前听学长讲的思路是用 $b i t s e t$ 优化暴力写，对于每一行的大小关系依次确定（第 $i$ 行大于第 $i - 1$ 行）。
也就是对于已经选择的列，确定了前 $i$ 行大小关系了，那就继续遍历剩下的列，使得能确定第 $i + 1$ 行关系（或者更多），前提是不会破坏后面的大小关系。用 $b i t s e t$ 优化这个过程以后复杂度是 $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;
}