注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj2771 Guardian of Decency 二分匹配之最大独立集  

2011-02-10 21:27:51|  分类: 图论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://poj.org/problem?id=2771

老师带学生出去旅游,但是担心学生会发生恋爱关系,所以带出去的学生至少要满足以下要求之中的一个:
1.身高相差40cm以上
2.同性
3.喜欢的音乐风格不同
4.喜欢的运动相同
问最多可以带出去多少学生?

个人感觉如果有男有女,就很有可能是二分匹配了。
这道题我们反过来想,如果将所有可能发生恋爱关系的男女配对,那么可以带出去的人数应该等于这个二分图的最大独立集。
根据公式: 最大独立集=顶点数(包括X和Y)-最大匹配
求一次匹配即可。

Source Code

Problem: 2771 User: 541780774
Memory: 1088K Time: 579MS
Language: G++ Result: Accepted

Source Code
 #include<stdio.h>   #include<stdlib.h>   #include<string.h>   #include <iostream>      using namespace std;      int nx, ny;             // X的點數目、Y的點數目    int mx[502], my[502];   // X各點的配對對象、Y各點的配對對象    bool vy[502];           // 紀錄Graph Traversal拜訪過的點    bool adj[502][502];     // 精簡過的adjacency matrix       // 以DFS建立一棵交錯樹    bool DFS(int x)    {        for (int y=0; y<ny; ++y)            if (adj[x][y] && !vy[y])            {                vy[y] = true;                   // 找到擴充路徑                  if (my[y] == -1 || DFS(my[y]))                {                   mx[x] = y; my[y] = x;                   return true;                   }            }        return false;    }       int bipartite_matching()    {        // 全部的點初始化為未匹配點。        memset(mx, -1, sizeof(mx));           memset(my, -1, sizeof(my));           // 依序把X中的每一個點作為擴充路徑的端點,        // 並嘗試尋找擴充路徑。        int c = 0;        for (int x=0; x<nx; ++x)   //     if (mx[x] == -1)    // x為未匹配點,這行可精簡。            {                // 開始Graph Traversal                memset(vy, false, sizeof(vy));                if (DFS(x)) c++;            }        return c;    }   struct{             int hi;             char mu[100];             char sp[100];           }p[2][501];   main()   {            int a,t,ans,n,mm,ff,i,j;            char x,y[100],z[100];            scanf("%d",&t);            while(t--)            {               memset(adj,0, sizeof(adj));              scanf("%d",&n);               mm=0;ff=0;              for(i=0;i<n;i++)              {                 scanf("%d",&a);                 cin>>x;                 cin>>y;                 cin>>z;                                 if(x=='M')                 {                                     p[0][mm].hi=a;                  strcpy(p[0][mm].mu,y);                  strcpy(p[0][mm].sp,z);                  mm++;                  }                  else                  {                                            p[1][ff].hi=a;                      strcpy(p[1][ff].mu,y);                      strcpy(p[1][ff].sp,z);                      ff++;                  }              }              for(i=0;i<mm;i++)              for(j=0;j<ff;j++)              {                  if( abs(p[0][i].hi-p[1][j].hi)<=40&&strcmp(p[0][i].mu,p[1][j].mu)==0&&strcmp(p[0][i].sp,p[1][j].sp)!=0)                  adj[i][j]=1;              }              nx=mm;              ny=ff;              printf("%d\n",n-bipartite_matching());                                      }            system("pause");     }   
  评论这张
 
阅读(173)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018