记录编号	272737	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的棋盘	最终得分	100
用户昵称	assassain	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2016-06-17 20:33:59	内存使用	0.38 MiB

#define MAXN 110UL
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m, t, N, tim, id[MAXN], rt[MAXN], vis[MAXN], w[MAXN][MAXN], mh[MAXN], d[MAXN];
bool rel[MAXN], tag[MAXN];

struct Edge { int hou, nt; } sg[5010];

bool cmp(int x, int y) {
	return rel[x]==rel[y]?x>y:rel[x]<rel[y];
}

void Add_edge(int x, int y) {
	sg[t] = (Edge){y, d[x]}, d[x] = t ++;
	return;
}

bool Dfs(int x) {
	for(int i = d[x] ; i != -1 ; i = sg[i].nt) if(vis[sg[i].hou]!=tim&&(!tag[sg[i].hou])) {
		vis[sg[i].hou] = tim;
		if((!mh[sg[i].hou])||Dfs(mh[sg[i].hou])) {
			mh[x] = sg[i].hou, mh[sg[i].hou] = x;
			return true;
		}
	}
	return false;
}

void Work() {
	memset(mh, 0, sizeof(mh));
	memset(tag, false, sizeof(tag));
    for(int i = 1 ; i <= N ; ++ i) if(!mh[i]) ++ tim, Dfs(i);
	for(int i = 1 ; i <= m ; ++ i) {
		for(int j = d[i] ; j != -1 ; j = sg[j].nt) if(!tag[sg[j].hou]) {
			if(mh[sg[j].hou]==i) {
				tag[i] = true, tag[sg[j].hou] = true;
				break;
			} else {
				int tmp = mh[sg[j].hou], pr = mh[i];
				mh[i] = sg[j].hou, mh[sg[j].hou] = i;
				tag[i] = true, tag[sg[j].hou] = true;
				mh[tmp] = 0, mh[pr] = 0;
				++ tim;
				if(Dfs(tmp)) break;
				else {
					tag[i] = false, tag[sg[j].hou] = false;
					mh[i] = pr, mh[pr] = i;
					mh[tmp] = sg[j].hou, mh[sg[j].hou] = tmp;
				}
			}
		}
	}
	return;
}

int main() {
	freopen("seed.in", "r", stdin);
	freopen("seed.out", "w", stdout);
	scanf("%d%d", &n, &m);
	N = max(n, m);
	for(int i = 1 ; i <= N ; ++ i) id[i] = i;
	for(int i = 1 ; i <= N ; ++ i) rt[i] = min(n, m);
	for(int i = 1 ; i <= n ; ++ i) {
		t = 0, memset(d, -1, sizeof(d));
		for(int j = m ; j >= 1 ; -- j) {
			memset(rel, false, sizeof(rel));
			for(int k = 1 ; k < i ; ++ k) rel[w[k][j]] = true;
			sort(id+1, id+N+1, cmp);
			for(int k = 1 ; k <= N && rel[id[k]] == false ; ++ k) Add_edge(j, id[k]+N);
		}
		for(int j = m+1 ; j <= N ; ++ j) {
			for(int k = N ; k >= 1 ; -- k) if(rt[k]!=n-i+1) Add_edge(j, k+N);
		}
		Work();
		for(int j = 1 ; j <= m ; ++ j) w[i][j] = mh[j]-N, -- rt[mh[j]-N], printf("%d ", mh[j]-N);
		puts("");
	}
	return 0;
}