首页 > 代码库 > bzoj 3816&&uoj #41. [清华集训2014]矩阵变换
bzoj 3816&&uoj #41. [清华集训2014]矩阵变换
稳定婚姻问题：
有n个男生，n个女生，所有女生在每个男生眼里有个排名，反之一样、
将男生和女生两两配对，保证不会出现婚姻不稳定的问题。
即A-1，B-2 而A更喜欢2，2更喜欢A。
算法流程：
每次男生向自己未追求过的排名最高女生求婚。
然后每个有追求者的女生在自己现男友和追求者中选择一个最喜欢的接受，然后拒绝其他人。
算法一定可以结束。
因为如果最后有一个男生单身，那他一定把所有女生都追求过一遍，说明没有女生单身，产生矛盾。
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#define inf 0x3f3f3f3f#define pb(x) push_back(x)using namespace std;int read(){ char c=getchar();int p=0; while(c<‘0‘||c>‘9‘)c=getchar(); while(c>=‘0‘&&c<=‘9‘)p=p*10+c-‘0‘,c=getchar(); return p;}int n,m;int map[205][405];int man[205][205];int wom[206][206];int ok[205],ko[205];int now[205];int num;vector<int>v[205];void solve(){ num=0; memset(ko,0,sizeof(ko)); memset(ok,0,sizeof(ok)); memset(now,0,sizeof(now)); for(int i=1;i<=n;i++)now[i]=1; while(num<n) { for(int i=1;i<=n;i++) { if(!ok[i]) { v[man[i][now[i]]].pb(i); now[i]++; } } for(int i=1;i<=n;i++) { int mn=-1; for(int j=0;j<v[i].size();j++) { if(mn==-1||wom[i][v[i][j]]<wom[i][mn])mn=v[i][j]; } if(mn!=-1) { if(!ko[i]||wom[i][mn]<wom[i][ko[i]]) { if(!ko[i])num++; ok[ko[i]]=0; ko[i]=mn; ok[mn]=i; } } v[i].clear(); } } for(int i=1;i<=n;i++) { printf("%d%c",ok[i]," \n"[i==n]); } puts(""); return ;}int main(){ int cas; scanf("%d",&cas); while(cas--) { memset(map,0,sizeof(map)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { int cnt=0; for(int j=1;j<=m;j++) { scanf("%d",&map[i][j]); if(map[i][j]!=0) { man[i][++cnt]=map[i][j]; wom[map[i][j]][i]=m-j; } } } solve(); } return 0;}
bzoj 3816&&uoj #41. [清华集训2014]矩阵变换
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。