设为首页 加入收藏

TOP

hdu1068 Girls and Boys --- 最大独立集
2015-07-20 18:05:16 来源: 作者: 【 】 浏览:9
Tags:hdu1068 Girls and Boys --- 最大 独立

有一个集合男和一个集合女,给出两集合间一些一一对应关系,问该两集合中的最大独立集的点数。

最大独立集=顶点总数-最大匹配数

此题中,若(a,b)有关,则(b,a)有关,每一个关系算了两次,相当于二分图的两边集合没有分男女,两边都是总人数,

所以此题中答案应该是 顶点总数-最大匹配数/2


#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          const int maxn=510; using namespace std; int mx[maxn],my[maxn],vis[maxn],e[maxn][maxn],n; int path(int i) { int j; for(j=0;j
         
          

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇POJ 2993 Emag eht htiw Em Pleh .. 下一篇HDOJ 3359 Kind of a Blur

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: