题解:有这样一个算法:
给定n个排列Ai和n个排列Bi,求一个排列p使得:
∀i,j∈[1,n],j̸=pi,Ai,pi<Ai,j∨Bk∣pk=j,j<Bi,j
可以在O(n2)时间内求出一组解。可以证明必定有解。
算法大致是,初始将所有数字push进队列。
对于队首元素x,尝试x没有尝试过的并且Ax,y最小的y。
如果y没有被选择,则令px=y并退出对x的尝试;
否则若Bz∣pz=y,y>Bx,y,则令px=y,并且将z∣pz=y放进队尾并退出对x的尝试;
否则对x继续尝试下一个y。
首先不难发现其算法复杂度由于对于x的选择越来越劣因此复杂度是O(n2)。同时正确性略(大雾)。
在这个题中,对行和颜色考虑,每行按照从左到右偏爱颜色,颜色按照出现的列从右向左偏向行。
然后直接运行上述算法即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define N 210
#define gc getchar()
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
inline int inn()
{
int x,ch;while((ch=gc)<'0'||ch>'9');
x=ch^'0';while((ch=gc)>='0'&&ch<='9')
x=(x<<1)+(x<<3)+(ch^'0');return x;
}
int pfx[N][N],pfy[N][N],a[N][N<<1],cntx[N],pt[N];
queue<int> q;int p[N],fr[N],vis[N],cnty[N];
int main()
{
for(int T=inn();T;T--)
{
int n=inn(),m=inn(),c;memset(cntx,0,sizeof(int)*(n+1));
rep(i,1,n) cnty[i]=n;memset(pt,0,sizeof(int)*(n+1));
memset(vis,0,sizeof(int)*(n+1));rep(i,1,n) rep(j,1,m) a[i][j]=inn();
rep(i,1,n) rep(j,1,m) if((c=a[i][j])) pfx[i][++cntx[i]]=c;
rep(j,1,m) rep(i,1,n) if((c=a[i][j])) pfy[c][i]=cnty[c]--;
while(!q.empty()) q.pop();rep(i,1,n) q.push(i);
for(int x,y;!q.empty();q.pop())
for(x=q.front(),p[x]=0;!p[x];)
if(!vis[y=pfx[x][++pt[x]]]) p[x]=y,fr[y]=x,vis[y]=1;
else if(pfy[y][x]<pfy[y][fr[y]]) p[x]=y,q.push(fr[y]),fr[y]=x;
rep(i,1,n) printf("%d ",p[i]);printf("\n");
}
return 0;
}