UVALive 3989 Ladies' Choice
amp 39 UVALive
2023-09-27 14:27:01 时间
经典的稳定婚姻匹配问题
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int maxn=1100; int n; int perfect_boy[maxn][maxn]; int perfect_girl[maxn][maxn]; int future_husband[maxn],future_wife[maxn]; int next[maxn]; queue<int> q; void engage(int boy,int girl) { int m=future_husband[girl]; if(m) { future_wife[m]=0; q.push(m); } future_husband[girl]=boy; future_wife[boy]=girl; } bool lover(int m1,int m2,int girl) { for(int i=1;i<=n;i++) { if(perfect_boy[girl][i]==m1) return true; if(perfect_boy[girl][i]==m2) return false; } } int main() { int T_T; scanf("%d",&T_T); while(T_T--) { scanf("%d",&n); memset(perfect_boy,0,sizeof(perfect_boy)); memset(perfect_girl,0,sizeof(perfect_girl)); memset(future_husband,0,sizeof(future_husband)); memset(future_wife,0,sizeof(future_wife)); memset(next,0,sizeof(next)); while(!q.empty()) q.pop(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&perfect_girl[i][j]); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) scanf("%d",&perfect_boy[i][j]); q.push(i); } while(!q.empty()) { int boy=q.front(); q.pop(); int girl=perfect_girl[boy][++next[boy]]; if(future_husband[girl]==0) engage(boy,girl); else { int m=future_husband[girl]; if(lover(boy,m,girl)) engage(boy,girl); else q.push(boy); } } for(int i=1;i<=n;i++) printf("%d\n",future_wife[i]); if(T_T) putchar(10); } return 0; }
相关文章
- 未经处理的异常在 System.Data.dll 中发生。其它信息:在应使用条件的上下文(在 '***' 附近)中指定了非布尔类型的表达式。
- What is the difference between readonly=“true” & readonly=“readonly”?
- 一些说明&其他奇奇怪怪的东西
- HDU 1009:FatMouse' Trade(简单贪心)
- 程序员之---C语言细节24(段错误、类型提升、sizeof 'A')
- 安装virtio驱动 & 升级内核
- STL - 常用关联容器代码 - set & multiset
- 【数据挖掘】时序模式-白噪音-时序图-ADF检验-一阶差分-acf && pacf(2021-11-11
- What's Dead & Exploded in Swift's exception stack?
- XSS 攻击实验 & 防御方案
- JS修改当前控件样式&为控件追加事件
- 运算符++的前缀、后缀和&的记录
- hdu 1165 Eddy's research II(数学题,递推)
- Invalid command 'WSGIScriptAlias', perhaps misspelled or defined by a module not included in the ser
- Android Studio集成SVN报错:can't use subversion command line client : svn
- AT&T联盟Ubuntu,开放网络大步走
- net.sf.json.JSONException: 'object' is an array. Use JSONArray instead
- svn: Can't convert string from 'UTF-8' to native encoding 解决的方法
- java.sql.SQLException:Column count doesn't match value count at row 1
- URAL 1684. Jack's Last Word KMP
- 【UVA】434-Matty's Blocks
- [CareerCup] 5.4 Explain Expression ((n & (n-1)) == 0) 解释表达式
- 学习笔记(05):Python网络编程&并发编程-基于socket实现简单套接字通信
- Java NIO —— TCP套接字(ServerSocketChannel & SocketChannel)