二分图匹配之稳定婚姻问题(题源,hdu1522)
发布日期:2021-10-24 15:11:32 浏览次数:15 分类:技术文章

本文共 2537 字,大约阅读时间需要 8 分钟。

老师布置了作业,让写下稳定婚姻问题的解答,GS算法的实现,正好hdu上有类似的题目,顺便拿来切了……

 

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1522 

 

很简单的方式,C++,用队列存储尚在单身的男士,退出条件为队列为空。 由于答案的输出一定要把男士放前面,所以又定义了个bres[]用来存储男士的选择,其实没有必要。

#include <cstring>
#include <stdio.h>
#include < string>
#include <cmath>  
#include <queue>   
#include <map>  
#include <memory>
#include <iostream>
using  namespace std;
map< stringint> bmap, gmap;
string bname[ 501], gname[ 501];
int bpre[ 501[ 501];     // used to store boys' prefrence, bpre[i][j] = k means to boy i, he ranks the girl k in jth place, the girl k is his jth choice.
int gpre[ 501][ 501];     // used to store girls' prefrence, gre[i][j] = k means to girl i, she ranks the boy j in the kth place
                    
// (different from the storing way of bpre[][], because to boys, they traverse girls from highest to lowest; 
                    
// but to girls, they need to quickly get to know one boy's rank)
int gres[ 501];     // used to store girls' result, gres[i]=j means girl i is with boy j
int bres[ 501];
char input[ 1500];
int n;
queue< int> bqueue;

int main(){
     while(~scanf( " %d ",&n)){
        memset(gres,- 1, sizeof gres);
        memset(bres,- 1, sizeof bres);
        getchar();
        bmap.clear();
        gmap.clear();
         int gcount =  0, i =  0, j =  0;
         int index =  0;
         for(i =  1;i <= n;i++){
            scanf( " %s ", input);
            bname[i] = input;
            bmap[input] = i;
            bqueue.push(i);
            bpre[i][ 0] =  1;     // b[i][0] store thes ranking number of the girl whom this boy is asking, every boy starts from the 1st girl.
             for(j =  1;j <= n;j++){
                scanf( " %s ",input);
                 if(gmap[input] ==  0){
                    index++;
                    gmap[input] = index;
                    gname[index] = input;
                }
                bpre[i][j] = gmap[input];
            }
        }
         for(i =  1;i <= n;i++){
            scanf( " %s ", input);
             int gindex = gmap[input];
             for(j =  1;j <= n;j++){
                scanf( " %s ",input);
                gpre[gindex][bmap[input]] = j;  // store the rank, the smaller, the higher the propriety will be.
            }
        }
         int bindex =  0, gaskindex =  0;
         while(!bqueue.empty()){
            bindex = bqueue.front();
             // cout << "current boy's name: "<< bname[bindex] <<endl;
            bqueue.pop();
            gaskindex = bpre[bindex][bpre[bindex][ 0]];
             if(gres[gaskindex] <  0){
                gres[gaskindex] = bindex;
                bres[bindex] = gaskindex;
            } else  if(gpre[gaskindex][bindex] < gpre[gaskindex][gres[gaskindex]]){
                bqueue.push(gres[gaskindex]);
                bpre[gres[gaskindex]][ 0] = (bpre[gres[gaskindex]][ 0]+ 1) % (n+ 1);
                gres[gaskindex] = bindex;
                bres[bindex] = gaskindex;
            } else{
                bqueue.push(bindex);
                bpre[bindex][ 0] = (bpre[bindex][ 0]+ 1) % (n+ 1);
            }
        }
         for(i =  1;i <=n ;i++){
            cout<<bname[i]<< '   '<<gname[bres[i]]<<endl;
        }
    }
     return  0;
}

去了注释代码还有1757B,罪过……

转载于:https://www.cnblogs.com/felixfang/archive/2012/04/21/2463811.html

转载地址:https://blog.csdn.net/weixin_30800807/article/details/94920941 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:20135202闫佳歆-第三章家庭作业-3.63
下一篇:WPF中Datagrid控件添加行号

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.249.70.76]2022年05月01日 18时22分56秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

mysql数据库 | 数据库优化 2019-12-19 17:39:55
mysql数据库 | MVCC 2019-12-19 17:39:56
JVM原理 | 逃逸分析 2019-12-19 17:39:54
mysql数据库 | 三大范式 2019-12-19 17:39:54
mysql数据库 | 数据库引擎简述 2019-12-19 17:39:54
mysql数据库 | 索引 2019-12-19 17:39:54
mysql数据库 | 锁相关 2019-12-19 17:39:55
【先看这个】目录页 2019-12-19 17:39:53
JVM原理 | JVM内存模型 2019-12-19 17:39:53
JVM原理 | GC机制 2019-12-19 17:39:53
JVM原理 | 类加载过程 2019-12-19 17:39:53
JVM原理 | 永久代和元空间区别 2019-12-19 17:39:53
JVM原理 | TLAB是什么 2019-12-19 17:39:53
多线程 & 线程经典案例 &锁 详细笔记 2019-12-19 17:39:52
红黑树 详细笔记 2019-12-19 17:39:52
常见排序算法总结 2019-12-19 17:39:52
跨域实现之JSONP/CORS模板代码及笔记 2019-12-19 17:39:52
java中常见锁的总结( 非常全 ) 2019-12-19 17:39:53
关于mysql数据库基础面试题的一些总结 2019-12-19 17:39:53
Ajax原生代码以及封装调用 2019-12-19 17:39:51