1175 - Ladies' Choice

链接

  稳定婚姻问题。

代码:

 #include<bits/stdc++.h>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ; int pref[N][N],order[N][N],Boys[N],Girls[N],cur[N];
queue<int>q; // 求婚队列 void Link(int u,int v) {
int t = Girls[v];
if (t) {
Boys[t] = ;
q.push(t);
}
Boys[u] = v;
Girls[v] = u;
} void solve() {
int n = read();
for (int i=; i<=n; ++i) {
for (int j=; j<=n; ++j)
pref[i][j] = read(); // 男孩心中第j个喜欢的女孩
cur[i] = ; // 求婚对象
Boys[i] = ; // 男孩的
q.push(i);
}
for (int i=; i<=n; ++i) {
for (int j=; j<=n; ++j) {
int t = read();
order[i][t] = j; // 男孩在女孩中的排名
}
Girls[i] = ; // 女孩的
}
while (!q.empty()) {
int u = q.front();q.pop();
int v = pref[u][cur[u]++];
if (!Girls[v]) Link(u,v);
else if (order[v][u] < order[v][Girls[v]]) Link(u,v);
else q.push(u);
}
while (!q.empty()) q.pop();
for (int i=; i<=n; ++i)
printf("%d\n",Boys[i]);
}
int main() {
int Case = read();
while (Case--) {
solve();
if(Case) puts("");
}
return ;
}

最新文章

  1. iOS自动处理键盘事件的第三方库:IQKeyboardManager
  2. MySQL Order By实现原理分析和Filesort优化
  3. SSMTP—让Linux系统从Office 365发送邮件
  4. SetConsoleCtrlHandler 处理控制台消息
  5. 怎样在WIN7系统下安装IIS和配置ASP(详细)
  6. 一句话输出NGINX日志访问IP前十位排行
  7. Java程序猿学习当中各个阶段的建议
  8. 【转】Python 中 Iterator和Iterable的区别
  9. maven 项目发布时,无法引用 修改的domain 问题
  10. 图片懒加载Demo
  11. awk进阶整理
  12. Tomcat NIO 模型的实现
  13. python中进制之间的转换
  14. cdn刷新和对应的浏览器现象
  15. (第六周)课上Scrum站立会议演示
  16. BZOJ5302 HAOI2018奇怪的背包(动态规划)
  17. 每日英语:China&#39;s Retirement Age Sets Experts at Odds
  18. spring概念简介、bean扫描与注册实现方式
  19. 个人学习jQuery笔记
  20. vivado sdk生成elf文件出错:make: Interrupt/Exception caught (code = 0xc00000fd, addr = 0x4227d3)

热门文章

  1. 【[SDOI2008]洞穴勘测】
  2. HDU 1083 Courses 【二分图完备匹配】
  3. SpringMVC学习记录三——8 springmvc和mybatis整合
  4. 【洛谷P1100】高低位交换
  5. CodeForces - 600B Queries about less or equal elements (二分查找 利用stl)
  6. vim_preview_window
  7. react(三):容器组件和傻瓜组件
  8. Openresty最佳案例 | 汇总
  9. mysql修改登录密码三种方式
  10. javascript--select标签的添加删除功能的使用