题目
题目链接：https://codeforces.com/problemset/problem/1500/C
给你两个 \(n\times m\) 的矩阵 \(A,B\)（\(1\le n,m\le 1500\)），矩阵的元素均为 \([1,n]\) 内的整数。
每一次操作你可以选定一列作为每一行的关键字，按照关键字从小到大的顺序把所有行排序得到一个新矩阵。这里使用的排序是稳定的，即如果有两行的关键字相同，则按照在原矩阵的先后顺序排序。
你可以进行不超过 \(5000\) 次操作，问你能否将 \(A\) 变成 \(B\)。不能变成输出 \(-1\)，否则输出一种可行的操作序列。
思路
首先可以把两个矩阵的每一行一一对应。如果有相同的行肯定是按照顺序对应，因为无论怎么排序他们之间相对顺序不会变。
记 \(B\) 矩阵第 \(i\) 行对应 \(A\) 矩阵第 \(id_i\) 行。
那么我们只需要让所有 \(id_i\) 行最后相对顺序小于 \(id_{i+1}\) 行。
对于 \(id_i\) 和 \(id_{i+1}\) 这两行，一个操作 \(j\)，可能会让他们之间的相对顺序变为正确的，变为错误的，或者不改变。我们只需要满足最后一次改变他们之间相对顺序的操作，是将他们相对顺序改为正确的即可。
显然一列最多拿来排序一次。考虑倒着处理。对于按照第 \(j\) 列排序这个操作，如果他会把 \(id_i\) 与 \(id_{i+1}\) 的相对顺序改为正确的，那么就从 \(j+n\) 向 \(i\) 连有向边；如果会改为错误的，就从 \(i\) 向 \(j+n\) 连有向边。
然后进行拓扑排序。注意这里对于 \(i\leq n\) 的点，只要被访问到一次就可以进队列了。
最后如果访问到了 \(n-1\) 个 \(\leq n\) 的点，说明有解，把拓扑序中 \(>n\) 的操作编号逆序输出即可。
注意可能到最后都存在 \(id_i\) 与 \(id_{i+1}\) 没有被任何操作改变相对顺序的情况，这时候就要判断他们初始顺序是否正确。
时间复杂度 \(O(nm)\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=3010;
const ull b1=131,p1=849322843;
const ull b2=13331,p2=1450295533;
const ull b3=1145141,p3=1839220993;
int n,m,cnt,tot,deg[N],head[N],a[N][N],id[N];
ull h1[2][N],h2[2][N],h3[2][N];
bool vis[N];
queue<int> q;
stack<int> st;
struct edge
{
int next,to;
}e[N*N];
void add(int from,int to)
{
e[++tot]=(edge){head[from],to};
head[from]=tot; deg[to]++;
}
void topsort()
{
for (int i=n+1;i<=n+m;i++)
if (!deg[i]) q.push(i);
while (q.size())
{
int u=q.front(); q.pop();
if (u<=n) cnt++;
else st.push(u-n);
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (v<=n && !vis[v])
vis[v]=1,q.push(v);
if (v>n)
{
deg[v]--;
if (!deg[v]) q.push(v);
}
}
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
h1[0][i]=(h1[0][i]*b1+a[i][j])%p1;
h2[0][i]=(h2[0][i]*b2+a[i][j])%p2;
h3[0][i]=(h3[0][i]*b3+a[i][j])%p3;
}
for (int i=1;i<=n;i++)
for (int j=1,x;j<=m;j++)
{
scanf("%d",&x);
h1[1][i]=(h1[1][i]*b1+x)%p1;
h2[1][i]=(h2[1][i]*b2+x)%p2;
h3[1][i]=(h3[1][i]*b3+x)%p3;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (h1[0][i]==h1[1][j] && h2[0][i]==h2[1][j] && h3[0][i]==h3[1][j])
{
id[j]=i; h1[1][j]=1145141919810LL;
break;
}
for (int i=1;i<n;i++)
for (int j=1;j<=m;j++)
{
if (a[id[i]][j]<a[id[i+1]][j]) add(j+n,i);
if (a[id[i]][j]>a[id[i+1]][j]) add(i,j+n);
}
topsort();
for (int i=1;i<n;i++)
if (!vis[i] && id[i]<id[i+1]) cnt++;
if (cnt<n-1) return printf("-1"),0;
printf("%d\n",(int)st.size());
for (;st.size();st.pop())
printf("%d ",st.top());
return 0;
}