university entrace examination(稳定婚姻匹配).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

const int MAX = 210;
int n,m;
struct node {
	int r,m;
	int sel;
	int k,f[60];
}stu[MAX];

struct node2 {
	int r,c;
	int total,s[MAX];
}sch[60];

int ac[MAX];

queue<int> SQ;
void gale_shapley()
{
	memset(ac,0,sizeof(ac));
	int i,j,k,sid;
	while(!SQ.empty()) {
		SQ.pop();
	}
	for(i=1;i<=n;i++) {
		SQ.push(i);
	}
	while(!SQ.empty()) {
		sid = SQ.front();
		SQ.pop();
		while(stu[sid].sel < stu[sid].k) {
			int uid = stu[sid].f[ stu[sid].sel ];
			if(sch[uid].total < sch[uid].c) {
				sch[uid].s[ sch[uid].total ++ ] = sid;
				ac[sid] = uid;
				break;
			}
			else {
				bool flag = false;
				for(j=0;j<sch[uid].c;j++) {
					int sid2 = sch[uid].s[j];
					if(stu[sid].r != sch[uid].r && stu[sid2].r == sch[uid].r) {
						if( !(stu[sid2].m > 0.7*stu[sid].m) ) {
							sch[uid].s[j] = sid;
							ac[sid2] = 0;
							ac[sid] = uid;
							SQ.push(sid2);
							flag = true;
							break;
						}
					}
					else {
						if(stu[sid].m > stu[sid2].m) {
							sch[uid].s[j] = sid;
							ac[sid2] = 0;
							ac[sid] = uid;
							SQ.push(sid2);
							flag = true;
							break;
						}
					}
				}
				if(flag) {
					break;
				}
				else {
					stu[sid].sel ++;
				}
			}
		}//while sel
	}//while
}

int main()
{
	int t,i,j;
	scanf("%d", &t);
	while(t --) {
		scanf("%d %d", &n, &m);
		for(i=1;i<=n;i++) {
			scanf("%d %d %d", &stu[i].r, &stu[i].m, &stu[i].k);
			for(j=0;j<stu[i].k;j++) {
				scanf("%d", &stu[i].f[j]);
			}
			stu[i].sel = 0;
		}
		for(i=1;i<=m;i++) {
			scanf("%d %d", &sch[i].r, &sch[i].c);
			sch[i].total = 0;
		}
		gale_shapley();
		for(i=1;i<=n;i++) {
			printf( ac[i]!=0 ? "%d\n" : "not accepted\n", ac[i]);
		}
		if(t > 0) {
			printf("\n");
		}
	}
}