hdu2939

source: http://acm.hdu.edu.cn/showproblem.php?pid=2939

title : Campus Recruit

 

/*
稳定婚配问题，延迟认可算法 
*/
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
const int WN = 1005;
const int MN = 1005;
const int M = 105;
const int N = 1005;
int now[MN], que[MN];
int m, n, p;
int wn, mn;
int num[M];
int sm[M][N], sn[N][M];
int id[N];
int s[WN][MN], like[MN][WN], wo[WN], st[M], in[N];
pii ps[WN];
//wn,mn分别女人和男人的人数，,s[i][j]是女人i对男人j打的分，liek[i]为第i个男人
//从最喜欢到最不喜欢的女人的下标,wo[i]最后表示第i个女人嫁的男人
void stableMatch(int wn, int mn, int s[WN][MN], int like[MN][WN], int wo[WN]){
	int cnt = mn+2, l, r, u, v, i;
	for(i = 0; i < wn; i++){
		wo[i] = -1;
	}
	for(l = r = 0; r < mn; r++){
		que[r] = r;
		now[r] = 0;
	}
	while(l != r){
		u = que[l];
		l = (l+1)%cnt;
		if(now[u] >= wn) continue; //这个男人找不到女人了
		v = like[u][now[u]];
		if(wo[v] == -1 || s[v][wo[v]] < s[v][u]){ //v更喜欢 u
			if(wo[v] >= 0){
				que[r] = wo[v];
				now[wo[v]]++;
				r = (r+1)%cnt;
			}
			wo[v] = u;
		}else{
			que[r] = u;
			r = (r+1)%cnt;
			now[u]++;
		}
	}
}
bool input(){
	scanf("%d%d", &m, &n);
	if(m == 0 && n == 0) return false;
	int i, j;
	for(i = p = 0; i < m; i++){
		scanf("%d", num+i);
		p += num[i];
	}
	for(i = 0; i < m; i++){
		for(j = 0; j < n; j++){
			scanf("%d", &sm[i][j]);
		}
	}
	for(i = 0; i < n; i++){
		for(j = 0; j < m; j++){
			scanf("%d", &sn[i][j]);
		}
	}
	return true;
}
bool cmppii(pii a, pii b){
	return a.first > b.first;
}
void  init(){
	int j, i, k, g, cnt;
	for(j = i = 0; i < m; i++){
		st[i] = j;
		for(k = j; k < j+num[i]; k++){
			id[k] = i;
			for(g = 0; g < n; g++){
				s[k][g] = sm[i][g];
			}
		}
		j += num[i];
	}
	for(i = 0; i < n; i++){
		cnt = 0;
		for(j = 0; j < m; j++){
			for(g = st[j]; g < st[j]+num[j]; g++){
				ps[cnt].first = sn[i][j];
				ps[cnt].second = g;
				cnt++;
			}
		}
		sort(ps, ps+cnt, cmppii);
		for(j = 0; j < cnt; j++){
			like[i][j] = ps[j].second;
		}
	}
}
void solve(){
	init();
	stableMatch(p, n, s, like, wo);
	int i;
	for(i = 0; i < n; i++) in[i] = 0;
	for(i = 0; i < p; i++){
		if(wo[i] >= 0){
			in[wo[i]] = id[i]+1;
		}
	}
	for(i = 0; i < n-1; i++){
		printf("%d ", in[i]);
	}
	printf("%d\n\n", in[i]);
}
int main(){
	while(input()) solve();
	return 0;
}