图论-二分图
关注
分享
扫一扫
文章平均质量分 87
acm_cxq
这个作者很懒，什么都没留下…
展开
-
匈牙利算法求二分图的最大匹配/匈牙利算法模板
二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。二分图的最大匹配：匈牙利算法 完美匹配： 如果所有点都在匹配边上，称这个最大匹配是完美匹配。 最小覆盖： 最转载 2016-07-26 17:46:01 · 1516 阅读 · 0 评论 -
hdu 3360 National Treasures（最小顶点覆盖，黑白染色）
National TreasuresTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1213 Accepted Submission(s): 434Problem DescriptionThe grea原创 2016-07-29 10:34:41 · 494 阅读 · 0 评论 -
hdu 2444 The Accomodation of Students（判断二分图，二分图最大匹配）
The Accomodation of StudentsTime Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5218 Accepted Submission(s): 2372Problem Description原创 2016-07-28 22:40:16 · 370 阅读 · 0 评论 -
hdu 2819 Swap（二分图最大匹配，输出路径）
SwapTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2712 Accepted Submission(s): 971Special JudgeProblem DescriptionGiven an原创 2016-07-29 08:22:36 · 546 阅读 · 0 评论 -
hdu 2236 无题II（二分法，枚举，二分图最大匹配）
无题IITime Limit: 2000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1515 Accepted Submission(s): 688Problem Description这是一个简单的游戏，在一个n*n的矩阵中，找原创 2016-07-28 11:35:10 · 773 阅读 · 0 评论 -
hdu 1669 Jamie's Contact Groups（二分+二分图最大多重匹配）
Jamie's Contact GroupsTime Limit: 15000/7000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 551 Accepted Submission(s): 189Problem DescriptionJami原创 2016-07-28 10:18:28 · 1189 阅读 · 0 评论 -
hdu 1281 棋盘游戏（枚举，二分图最大匹配）
棋盘游戏Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4094 Accepted Submission(s): 2397Problem Description小希和Gardon在玩一个游戏：对一个N*原创 2016-07-28 09:11:49 · 391 阅读 · 0 评论 -
hdu 1507 Uncle Tom's Inherited Land*（二分图最大匹配，黑白染色）
Uncle Tom's Inherited Land*Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3214 Accepted Submission(s): 1351Special JudgeProblem原创 2016-07-28 00:09:29 · 408 阅读 · 0 评论 -
hdu 1498 50 years, 50 colors（枚举，最小顶点覆盖）
50 years, 50 colorsTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2253 Accepted Submission(s): 1264Problem DescriptionOn Oct原创 2016-07-27 22:57:53 · 438 阅读 · 0 评论 -
hdu 1068 Girls and Boys（最大独立集模板）
Girls and BoysTime Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 10501 Accepted Submission(s): 4850Problem Descriptionthe seco原创 2016-07-27 22:21:08 · 507 阅读 · 0 评论 -
hdu 2768 Cat vs. Dog（最大独立集）
Cat vs. DogTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2026 Accepted Submission(s): 771Problem DescriptionThe latest real原创 2016-07-27 21:54:21 · 490 阅读 · 0 评论 -
hdu 3729 I'm Telling the Truth（二分图最大匹配，字典序最大输出）
I'm Telling the TruthTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1997 Accepted Submission(s): 1007Problem DescriptionAfte原创 2016-07-27 21:11:52 · 731 阅读 · 0 评论 -
poj 3041 Asteroids（ 最小顶点覆盖，二分图）
AsteroidsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 20107 Accepted: 10905DescriptionBessie wants to navigate her spaceship through a dangerous as原创 2016-07-27 10:58:54 · 486 阅读 · 0 评论 -
poj 2446 Chessboard（二分图最大匹配）
ChessboardTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 16624 Accepted: 5171DescriptionAlice and Bob often play games on chessboard. One day, Alice原创 2016-07-27 09:57:38 · 502 阅读 · 0 评论 -
poj 2536 Gopher II（二分图最大匹配，构图）
Gopher IITime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 8347 Accepted: 3444DescriptionThe gopher family, having averted the canine threat, must face原创 2016-07-26 21:04:41 · 495 阅读 · 0 评论 -
hdu 3605 Escape/poj 2584 T-Shirt Gumbo（二分图多重匹配）
EscapeTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 8670 Accepted Submission(s): 2000Problem Description2012 If this is the原创 2016-07-26 20:37:50 · 412 阅读 · 0 评论 -
hdu 2239 Selecting Courses（二分图最大匹配）
Selecting CoursesTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 10127 Accepted: 4557DescriptionIt is well known that it is not easy to select courses原创 2016-07-26 19:43:22 · 510 阅读 · 0 评论 -
poj 1274 The Perfect Stall（匈牙利算法模板）
The Perfect StallTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 22896 Accepted: 10202DescriptionFarmer John completed his new barn just last week, co原创 2016-07-26 17:47:43 · 385 阅读 · 0 评论 -
hdu 1151 Air Raid（最小路径覆盖）
Air RaidTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4731 Accepted Submission(s): 3170Problem DescriptionConsider a town w原创 2016-07-29 13:04:59 · 343 阅读 · 0 评论