【二分匹配】HDU1068-Girls and Boys

说说什么是最大独立集

在二分图中,
独立集指的是两两之间没有边的顶点的集合,
顶点最多的独立集成为最大独立集。
二分图的最大独立集=节点数-最大匹配数

例子:
1
2 - 1'
3 - 2'
4 - 3'   
    4'
最大独立集=8-3=5.
最大独立集是1,2,3,4,4'

 

例题:
Girls and Boys
Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7486    Accepted Submission(s): 3419

Problem Description
the second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying
the condition: there are no two students in the set who have been “romantically involved”. The result of the program is the number of students in such a set.

The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description:

the number of students
the description of each student, in the following format
student_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 student_identifier3 ...
or
student_identifier:(0)

The student_identifier is an integer number between 0 and n-1, for n subjects.
For each given data set, the program should write to standard output a line containing the result.

 

Sample Input
7
0: (3) 4 5 6
1: (2) 4 6
2: (0)
3: (0)
4: (2) 0 1
5: (1) 0
6: (2) 0 1
3
0: (2) 1 2
1: (1) 0
2: (1) 0
 

Sample Output
5
2
 

Source
Southeastern Europe 2000
 

 

 

 

依旧是二分匹配,用匈牙利算法。。。。
等等,好像没有所谓的集合A和集合B了,好像所有人都在相互喜欢= =
就是说0 喜欢 4 5 6,4 5 6也喜欢 0。。。。也就是说这里的数字是
不分男女的。。。仅仅是数字喜欢数字(暂且这么看吧)
这就有影响了,假设0选择了4做匹配,那么4只能选0做匹配了。。。。
这就把原来的二分图匹配变成了“一分图”匹配。。。(自己起得名= =)
这样,按原来匈牙利的做法,求出来是男数字与女数字之间的匹配,
所以只要将匹配的结果除以2,就是所谓的“一分图”匹配数量,
就可以用刚刚的公式:二分图的最大独立集=节点数-最大匹配数

AC代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int line[1100][1100],used[1100],boy[1100];
int n;//全局变量和局部变量不要使用相同名称的变量,否则导致结果出错
int Find(int x)
{
    int i;
    for(i=0;i<n;i++)
    {
       if(line[x][i]==1&&used[i]==0)
       {
           used[i]=1;
           if(boy[i]==0||Find(boy[i]))
           {
              boy[i]=x;
              return 1;
           }
       }
    }
    return 0;
}
int main()
{
    int i,j,x,y,z,sum;
    while(scanf("%d",&n)!=EOF)
    {
        memset(line,0,sizeof(line));
        memset(boy,0,sizeof(boy));
        for(i=0;i<n;i++)
        {
           scanf("%d: (%d)",&x,&y);
           while(y--)
           {
              scanf("%d",&z);
              line[x][z]=1;//x跟z暧昧
              line[z][x]=1;
           }
        }
        /*for(i=0;i<n;i++)//检测一下谁和谁暧昧.....
        {
           for(j=0;j<n;j++)
           if(line[i][j]==1)
           printf("%d LOVE %d\n",i,j);
        }*/
        sum=0;
        for(i=0;i<n;i++)
        {
           memset(used,0,sizeof(used));
           if(Find(i)) sum++;//找到可以结合的就记录
        }
        //因为此题是单集合的,所以不能够按照平常的求最大独立集
        //的方法,要除以2(因为实际上是一分图而不是二分图....)
        printf("%d\n",n-sum/2);
    }
    return 0;
} 
时间: 2024-11-13 14:33:28

【二分匹配】HDU1068-Girls and Boys的相关文章

二分匹配最大匹配的理解(附图解)

  定义 一个PXP的有向图中,路径覆盖就是在图中找一些路径,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之关联:(如果把这些路径中的每条路径从它的起始点走到它的终点,那么恰好可以经过图中的每个顶点一次且仅一次):如果不考虑图中存在回路,那么每条路径就是一个弱连通子集. 由上面可以得出: 1.一个单独的顶点是一条路径: 2.如果存在一路径p1,p2,......pk,其中p1 为起点,pk为终点,那么在覆盖图中,顶点p1,p2,......pk不再与其它的顶点之间存在有向边. 路径

【算法导论】最大二分匹配

        最大二分匹配问题在现实生活中比较普遍,常常出现在任务分配上.例如,有5个员工,4个不同的任务,而不同员工能够完成不同或相同的任务.也就是说,有的员工只会做这个任务,有的员工会做那个任务,有的员工会做一些任务.图解如下:左边代表员工,右边代表任务,连线代表有能力完成.   我们的问题是合理安排员工,尽可能地完成最多的任务数.上图中阴影部分为一种最好的分配方式.前一篇文章中,我们介绍了最大流问题,在这里我们可以将最大二分匹配问题转变成最大流问题.具体如下图所示:   其中每条边的最大

【二分匹配】HDU1083-Courses

Courses Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3645    Accepted Submission(s): 1745 Problem Description Consider a group of N students and P courses. Each student visits zero, one or

poj 2226 Muddy Fields(合理建图+二分匹配)

/* 题意:用木板盖住泥泞的地方,不能盖住草.木板任意长!可以重叠覆盖! '*'表示泥泞的地方,'.'表示草! 思路: 首先让我们回忆一下HDU 2119 Matrix这一道题,一个矩阵中只有0, 1,然后让我们通过选择一行,或者 是一列将其所在行的或者所在列的 1全部删掉,求出最少需要几步? 这道题的思路就是:将行标 和 列标值为1的建立一条边!通过匈牙利算法可以得到这个二分图的最大匹配数 最大匹配数==最小顶点覆盖数!最小顶点覆盖就是用最少的点覆盖了这个二分图的所有的边,然后去掉这些 最小覆

hdu 1068 Girls and Boys

       求最大独立集,因为题意是男女之间关系,所以是二分图(也许那时还没有搞基吧--)这题就是最大独立集=n-(最大覆盖集=最大匹配)      和hdu1054几乎一模一样   /* author:jxy lang:C/C++ university:China,Xidian University **If you need to reprint,please indicate the source** */ #include <iostream> #include <cstdio

图的匹配问题与最大流问题(五)计算二分图的最大匹配

二分图的最大匹配问题第一篇已经说过,下面看看百度百科给的一些解释: 给定一个二分图G,M为G边集的一个子集,如果M满足当中的任意两条边都不依附于同一个顶点,则称M是一个匹配. 极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数.最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配.选择这样的边数最大的子集称为图的最大匹配问题. 如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配

HDU2063-过山车

过山车 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10683    Accepted Submission(s): 4699 Problem Description RPG girls今天和大家一起去游乐场玩,终于可以坐上梦寐以求的过山车了.可是,过山车的每一排只有两个座位,而且还有条不成文的规矩, 就是每个女生必须找个个男生做p

数学建模十大算法

作者:July  二零一一年一月二十九日   一.蒙特卡罗算法1946年,美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis 共同发明了,蒙特卡罗方法. 此算法被评为20世纪最伟大的十大算法之一,详情,请参见我的博文:http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6127953.aspx   蒙特卡罗方法(Monte Carlo method),又称随机抽样或统计模拟方法

Pregel: A System for Large-Scale Graph Processing

作者Grzegorz Malewicz, Matthew H. Austern .etc.Google Inc 2010-6 原文http://people.apache.org/~edwardyoon/documents/pregel.pdf 译者phylips@bmy 2012-09-14 译文http://duanple.blog.163.com/blog/static/70971767201281610126277/ [说明Pregel这篇是发表在2010年的SIGMOD上Pregel这