C++14(g++5.4) 解法, 执行用时: 2875ms, 内存消耗: 1252K, 提交时间: 2018-10-22 22:37:13

#include<bits/stdc++.h>
using namespace std;
const int N=233;
int n,m,tim,ans[N],bel[N],vis[N],g[N],pre[N][N],nxt[N][N];
void del(int x,int y)
{
	if(g[x]==y)g[x]=nxt[x][y];
	else nxt[x][pre[x][y]]=nxt[x][y],pre[x][nxt[x][y]]=pre[x][y];
}
bool dfs(int x,int mn)
{
	for(int i=g[x];i;i=nxt[x][i])
	if(vis[i]!=tim)
	{
		vis[i]=tim;
		if(!bel[i]||bel[i]>mn&&dfs(bel[i],mn))
		{bel[i]=x;ans[x]=i;return 1;}
	}
	return 0;
}
void work()
{
	for(int i=1;i<=n;i++)tim++,dfs(i,0);
	for(int i=1;i<=n;i++)
	{
		++tim;
        for(int j=g[i];j;j=nxt[i][j])
        if(bel[j]==i)break;
		else if(bel[j]>i)
		{
			int x=bel[j],y=ans[i];
			bel[ans[i]]=ans[bel[j]]=0;
			bel[j]=i,ans[i]=j;
			if(dfs(x,i))break;
			ans[x]=j,bel[j]=x;
			bel[y]=i,ans[i]=y;
		}
	}
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		memset(pre,0,sizeof pre);
		memset(nxt,0,sizeof nxt);
		for(int i=1;i<=n;i++)g[i]=1;
		for(int i=1;i<=n;i++)
		for(int j=2;j<=n;j++)
		nxt[i][j-1]=j,pre[i][j]=j-1;
		for(int i=1;i<=m;i++)for(int j=1,x;j<=n;j++)scanf("%d",&x),del(j,x);
		for(int i=m+1;i<=n;i++)
		{
			tim=0;
			memset(ans,0,sizeof ans);
			memset(bel,0,sizeof bel);
			memset(vis,0,sizeof vis);
			work();
			for(int j=1;j<=n;j++)del(j,ans[j]);
			for(int j=1;j<=n;j++)printf("%d ",ans[j]);
			puts("");
		}
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 2545ms, 内存消耗: 1236K, 提交时间: 2018-10-22 09:56:50

#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define mset(x,y) memset(x,y,sizeof(x))
using namespace std;
const int N=225;
int n,m,x,tim,head[N],nxt[N][N],pre[N][N],bel[N],val[N],vis[N];
void del(int i,int j){
	if (head[i]==j) head[i]=nxt[i][j];
	else nxt[i][pre[i][j]]=nxt[i][j],pre[i][nxt[i][j]]=pre[i][j];
}
bool dfs(int u,int lim){
	for (int i=head[u];i;i=nxt[u][i]) if (vis[i]!=tim){
		vis[i]=tim;
		if (!bel[i]||bel[i]>lim&&dfs(bel[i],lim)) return val[u]=i,bel[i]=u,1;
	}
	return 0;
}
void work(){
	rep (i,1,n) tim++,dfs(i,0);
	rep (i,1,n){
		tim++;
		for (int j=head[i];j;j=nxt[i][j]){
			if (bel[j]==i) break;
			if (bel[j]<i) continue;
			int x=bel[j],y=val[i];
			val[i]=j,bel[j]=i; val[x]=bel[y]=0;
			if (dfs(x,i)) break;
			val[x]=j,bel[j]=x,bel[y]=i,val[i]=y;
		}
	}
}
int Main(){
	scanf("%d%d",&n,&m);
	rep (i,1,n){
		rep (j,2,n) nxt[i][j-1]=j,pre[i][j]=j-1; nxt[i][n]=0;
		head[i]=1;
	}
	rep (i,1,m) rep (j,1,n) scanf("%d",&x),del(j,x);
	rep (i,m+1,n){
		tim=0,mset(val,0),mset(bel,0),mset(vis,0);
		work();
		rep (j,1,n) del(j,val[j]);
		rep (j,1,n) printf("%d%c",val[j]," \n"[j==n]);
	}
	return 0;
}
int main(){
	int T; scanf("%d",&T); while (T--) Main();
	return 0;
}