Sicily 1224 速配游戏 (SOJ 1224)「暴力匹配」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/185

原题地址:点击打开链接

期末考试结束,各种手尾也收拾得差不多了,再过一阵子就往北京去了。最开心的是新一届的班委也终于敲定,我一个人谈了5个班委,百发百中十分高兴!班务后继有人心头大石就可以放下!在此希望10计科B班的新一届班委能够工作顺利、收获良多~!

最近又想了一些MSRA的事情,将要去那里了内心比较兴奋&激动,不过同时又会有些担心,因为不知道自己能不能做好吧,而且5年的博士生涯,应该十分漫长,不过5年的时间我就不信自己做不出成绩。现在我还是想将来从研究转去产品开发,不过不知道到时候会不会身不由己,ANYWAY目前先专攻研究是肯定的啦哈哈。

话说我蛋疼又报了微软的探星夏令营,因为我发现时间是3天而且又可以选在北京,后天就笔试了,呃,不知道会不会被微软鄙视。因为我发现我真的太水了,上人人和微博看了一下树嘉的主页,浏览下来又是项目、又是看论文,各种TSP,kinetc,3D什么的,prototype都做出来了,现在真的是差太远啊!人家报了广研班最后还直接和企鹅说再见,我嘛,是实习招聘二面直接让别人和我说再见,差距可想而知。

有时候为什么我会迟睡呢,除了一部分是混着混着就迟了外,另外一部分是因为去看几个牛人的微博+人人,感受到差距后感叹一番,然后又下定决心努力追赶,想着想着就迟了。我是一个不懂得鞭策自己的人,总是要看到别人的厉害才会知道往前赶,这样不行啊!我又想起吖水的一条状态——“要么前进,要么倒下,不能拼搏,不如回家”

我发现自己不少题解前面一大段都是日志,唔,要不要分开呢……算了,正文见下

——————正文——————

这题还是比较好的,个人感觉,虽然没有什么固定的章法来做,但是要一下子理顺解题思路不是件容易的事,我一开始想的时候就是思维打结。

不过建立好模型之后,这题的思路会清晰很多,其实就是两个矩阵。

一个矩阵,是属于男人的,不妨叫male,另外一个是属于女人的,叫female。最直观的想法就是male和female的内容就对应输入的内容,因为输入本身就是输入两个矩阵。然后就是找到让矩阵之间产生联系的方法。从题目来看,就感觉女人占绝对优势,因为最终要不要某个man,是这个女人说了算,在没有碰到最好的之前,她竟然可以不接受也不拒绝,等到碰到更好的就一把甩掉,不公平啊!

所以一开始我是主要着力于以female这个矩阵作为解题的,那么对于每个女人,依次遍历她心仪的男人,然后看一下当前这一轮谁的分数最高,然后将他保留,其他的男人则拒绝,让他们选下一个女人。(我觉得久没写博客,语言又臭又长又没有讲中重点)问题在于这样的遍历方法复杂度是O(n*n*k),首先每次女人都要遍历心仪表,为O(n*n),然后最多被拒绝的,k是经过多少轮,而题目中给的5秒,大概就能撑到5*10^8,如果k达到500,那多少有点危险,然而,k最大可能去到n*n,因为男人的矩阵是n*n的,而且这里的遍历里面还有其它的操作,因此这里复杂度可能去到O(n^4),但是有一个可以优化的地方就是对于每个女人来说,她们实际不需要遍历她们的心仪表,只需要在这一轮选她的男人中,排出个高低美丑就可以了。

所以稍稍转变一下,每次以男人为主,我们可以用一个标记数组,标记每个男人当前打算求婚的对象是谁(这个标记从1开始,只会一直增大,因为男人不能够重新选择之前他们求过婚但被拒绝的女人),知道每个男人当前的求婚对象,我们就可以知道用一个数组记录某个女人在某一轮接受到谁的求婚,并且在这些人中,哪个是最中意的。有了这些数据,我们就可以针对每个女人当前的求婚对象,对于不中意的,他们的标记全部加1,检查完所有的女人后,开始新的一轮,重新迭代。

停止条件是什么呢?就是每个女人有且仅有一个男人求婚,这样即便再迭代,情况也不会变,因为标记是不会变的,下一轮迭代男人的选择和当前是一样的。这个时候就可以结束了,然后直接输出男人的标记中记录的当前的女人即可。算一下复杂度,每一轮要对n个男人检查,检查时只关联一个女人,这里复杂度是O(n),而对于这些女人,每一轮最多要拒绝掉(n-1)个男人,使他们的标记加1,那么复杂度也是O(n),这样的求婚过程最多执行n*n轮(上述的k轮),因为所有男人的所有下标移动次数之和最大是n*n次,则复杂度的上界是O(n*n*2n),即O(n^3),比之前说的方法好一级。

需要注意的是,输入数据中,男人和女人的编号是从1开始的。更多内容参见注释

下面直接上代码了:

#include<iostream>
#include<stdio.h>
#include<memory.h>
#define MAXN 1005
using namespace std;
int point[MAXN];		 //标记,point[i]用于记录第i号男人选择心仪表中的第几号女人
int male[MAXN][MAXN];	 //male[i][j]表示第i号男人的排名为j的女人的号码
int female[MAXN][MAXN];  //female[i][j]表示第i号女人对第j号男人的排名,和male的表示不同
int sel[MAXN];           //sel[i]表示,当前一轮中,第i号女人暂时选择的男人编号
int follow[MAXN][MAXN];  //follow[i]表示第i号女人当前这一轮的追求者
int follow_index[MAXN];  //follow_index[i]表示第i好女人当前这一轮有多少追求者
int n,tmp;
int main()
{
     //freopen("in","r",stdin);
     //freopen("out","w",stdout);
     while(scanf("%d",&n)!=EOF)
     {
       for(int i=1;i<=n;++i)
         for(int j=1;j<=n;++j)
           scanf("%d",&male[i][j]);
       for(int i=1;i<=n;++i)  
         female[i][0]=MAXN;
       for(int i=1;i<=n;++i)
         for(int j=1;j<=n;++j)
         {
            scanf("%d",&tmp);
            female[i][tmp]=j;
         }
       for(int i=1;i<=n;++i)
         point[i]=1;
       int select=0;
       while(select!=n)
       {
         select=0;
         memset(follow_index,0,sizeof(follow_index));
         memset(sel,0,sizeof(sel));
         for(int i=1;i<=n;++i)
         {
           tmp=male[i][point[i]]; //the preferred woman
           follow[tmp][follow_index[tmp]++]=i;
           if(female[tmp][sel[tmp]]>female[tmp][i])
             sel[tmp]=i;
         }
         for(int i=1;i<=n;++i)
         {
           if(sel[i])
             select++;
           for(int j=0;j<follow_index[i];++j)
           {
              tmp=follow[i][j];
              if(tmp!=sel[i])
                point[tmp]++;
           }
         }
       }//finished
       for(int i=1;i<=n;++i)
         printf("%d\n",male[i][point[i]]);
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注