UVA 1175 - Ladies' Choice
2024-09-01 07:22:38
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 ;
}
最新文章
- iOS自动处理键盘事件的第三方库:IQKeyboardManager
- MySQL Order By实现原理分析和Filesort优化
- SSMTP—让Linux系统从Office 365发送邮件
- SetConsoleCtrlHandler 处理控制台消息
- 怎样在WIN7系统下安装IIS和配置ASP(详细)
- 一句话输出NGINX日志访问IP前十位排行
- Java程序猿学习当中各个阶段的建议
- 【转】Python 中 Iterator和Iterable的区别
- maven 项目发布时,无法引用 修改的domain 问题
- 图片懒加载Demo
- awk进阶整理
- Tomcat NIO 模型的实现
- python中进制之间的转换
- cdn刷新和对应的浏览器现象
- (第六周)课上Scrum站立会议演示
- BZOJ5302 HAOI2018奇怪的背包(动态规划)
- 每日英语:China&#39;s Retirement Age Sets Experts at Odds
- spring概念简介、bean扫描与注册实现方式
- 个人学习jQuery笔记
- vivado sdk生成elf文件出错:make: Interrupt/Exception caught (code = 0xc00000fd, addr = 0x4227d3)
热门文章
- 【[SDOI2008]洞穴勘测】
- HDU 1083 Courses 【二分图完备匹配】
- SpringMVC学习记录三——8	springmvc和mybatis整合
- 【洛谷P1100】高低位交换
- CodeForces - 600B Queries about less or equal elements (二分查找 利用stl)
- vim_preview_window
- react(三):容器组件和傻瓜组件
- Openresty最佳案例 | 汇总
- mysql修改登录密码三种方式
- javascript--select标签的添加删除功能的使用