hdu2063 最大二分匹配(匈牙利算法)

过山车

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 30799    Accepted Submission(s): 13289

Problem Description

RPG girls今天和大家一起去游乐场玩,终于可以坐上梦寐以求的过山车了。可是,过山车的每一排只有两个座位,而且还有条不成文的规矩,就是每个女生必须找个个男生做partner和她同坐。但是,每个女孩都有各自的想法,举个例子把,Rabbit只愿意和XHD或PQK做partner,Grass只愿意和linle或LL做partner,PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题,boss刘决定只让找到partner的人去坐过山车,其他的人,嘿嘿,就站在下面看着吧。聪明的Acmer,你可以帮忙算算最多有多少对组合可以坐上过山车吗?

Input

输入数据的第一行是三个整数K , M , N,分别表示可能的组合数目,女生的人数,男生的人数。0<K<=1000
1<=N 和M<=500.接下来的K行,每行有两个数,分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。

Output

对于每组数据,输出一个整数,表示可以坐上过山车的最多组合数。

Sample Input

6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0

Sample Output

3

匈牙利算法详解:https://blog.csdn.net/dark_scope/article/details/8880547

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=505;
int line[N][N];
int girl[N],used[N];
int k,m,n;
bool found(int x)
{
    for(int i=1; i<=n; i++)
    {
        if(line[x][i]&&!used[i])//x与i之间是否有连线,并且男生i没有被匹配过(第一个女生与她联系的第一个男生配对)
        {
            used[i]=1;//标记男生i被匹配过
            if(girl[i]==0||found(girl[i]))//第i个女生还没有匹配或者第I个女生匹配了就回溯
            {//先让I女生和X男匹配,再让I-1女生和与她联系的第二个男生匹配
                girl[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int x,y;
    while(scanf("%d",&k)&&k)
    {
        scanf("%d %d",&m,&n);
        memset(line,0,sizeof(line));
        memset(girl,0,sizeof(girl));
        for(int i=0; i<k; i++)
        {
            scanf("%d %d",&x,&y);
            line[x][y]=1;
        }
        int sum=0;
        for(int i=1; i<=m; i++)
        {
            memset(used,0,sizeof(used));
            if(found(i))
             sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}

相似题目:

E: DATE ALIVE

Time Limit: 1 s      Memory Limit: 128 MB

Problem Description

五河士道家里的精灵越来越多了,而每一个精灵都想和他有一个约会。然而五河士道却只有一个,无奈之下只能使出分身帮自己解围。

不过并不是所有的精灵都同意这样做,有些精灵不愿意和士道分身进行约会,也有部分精灵同时选择同一个分身进行约会。

假设有N个分身,精灵的数量为M,可能的约会组合有K组。

设N=3,M=5,K=5,可能的组合为1-1,1-3,2-4,3-4,3-5(如下图),为了避免冲突,我们最多可以选择1-1,2-4,3-5一共三种组合(或者是1-3,2-4,3-5)

那么请设计一个程序判断每一次可能的组队最多能确定多少队伍?最后,让我们的约会开始吧~

Input

输入N,M,K

N,M,K为正整数

1<=N<=500

1<=M<=500

接下来K行,输入u,v,表示uv之间愿意组队

u在N的范围内,v在M的范围内

Output

输出最大组队数目

Sample Input

3 5 5
1 1
1 3
2 4
3 4
3 5

Sample Output

3

原文地址:https://www.cnblogs.com/-citywall123/p/10034516.html

时间: 11-28

hdu2063 最大二分匹配(匈牙利算法)的相关文章

HDU 3729 二分匹配匈牙利算法

I'm Telling the Truth Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1482    Accepted Submission(s): 740 Problem Description After this year’s college-entrance exam, the teacher did a survey in

hdu 2063 (二分匹配 匈牙利算法)

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

hihocoder 1122最大二分匹配匈牙利算法

#include <cstdio> #include <iostream> #include <algorithm> #include <queue> #include <cmath> #include <cstring> #include <stack> #include <set> #include <map> #include <vector> using namespace st

USACO 4.2 The Perfect Stall(二分图匹配匈牙利算法)

The Perfect StallHal Burch Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering problems, all the stalls in the new barn are different. For the first week, Farmer John r

HDU 5943 Kingdom of Obsession 【二分图匹配 匈牙利算法】 (2016年中国大学生程序设计竞赛(杭州))

Kingdom of Obsession Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 49    Accepted Submission(s): 14 Problem Description There is a kindom of obsession, so people in this kingdom do things very

矩阵游戏|ZJOI2007|BZOJ1059|codevs1433|luoguP1129|二分图匹配|匈牙利算法|Elena

1059: [ZJOI2007]矩阵游戏 Time Limit: 10 Sec  Memory Limit: 162 MB Description 小Q是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏--矩阵游戏.矩阵游戏在一个N *N黑白方阵进行(如同国际象棋一般,只是颜色是随意的).每次可以对该矩阵进行两种操作:行交换操作:选择 矩阵的任意两行,交换这两行(即交换对应格子的颜色)列交换操作:选择矩阵的任意行列,交换这两列(即交换 对应格子的颜色)游戏的目标,即通过若干次操作,

网络流24题 第一题 - 洛谷2756 飞行员配对方案 二分图匹配 匈牙利算法

欢迎访问~原文出处--博客园-zhouzhendong 去博客园看该题解 题目传送门 题意概括 裸的二分图匹配 题解 匈牙利算法 上板子 代码 #include <cstring> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cmath> using namespace std; const int N=100+5; int m,n,a,b,match[N

图论-二分图匹配-匈牙利算法

有关概念: 二分图:图G中的点集可以分为两个互不相交的子集,且G中的每条边连接的两个点分别属于这两个子集 二分图匹配:二分图G的子图M中每个结点上只连一条边,则称M为一个匹配 极大匹配:无法再向二分图中加边且满足匹配条件的匹配 最大匹配:所有极大匹配中边数最多的一个 增广路:若P为图G上连接两个未匹配结点的路径,且已匹配边和未匹配边在P上交替出现,则称P为相对于M的一条增广路 匈牙利算法即用来求二分图的极大匹配 思路: 在图G中找出增广路P,对P上每一条边取反(即已匹配边改为未匹配边,未匹配边改

二分图匹配(匈牙利算法) POJ 3020 Antenna Placement

题目传送门 1 /* 2 题意:*的点占据后能顺带占据四个方向的一个*,问最少要占据多少个 3 匈牙利算法:按坐标奇偶性把*分为两个集合,那么除了匹配的其中一方是顺带占据外,其他都要占据 4 */ 5 #include <cstdio> 6 #include <algorithm> 7 #include <cstring> 8 #include <vector> 9 using namespace std; 10 11 const int MAXN = 4e

UVALive5874 - Social Holidaying-二分图匹配/匈牙利算法

有n个家庭,m个房间,一个房间只能两个家庭住.求最大匹配. 比较标准的二分图问题.先初始化把可能的家庭建边,然后跑一边匈牙利算法. 最后的答案是最大匹配数/2,因为建图时有重复. #include <cstdio> #include <algorithm> #include <cstring> #include <map> using namespace std; const int MAXN = 410; int uN,vN; int g[MAXN][MA