回归梦想

分类

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2) 题解(271)

/ 注册

TA的专栏 41篇文章 0人订阅

16篇文章 978人学习

牛客每日一题

6篇文章 776人学习

0篇文章 0人学习

0篇文章 0人学习

0篇文章 0人学习

3篇文章 685人学习

ACwing寒假每日一题（提高组）

3篇文章 780人学习

13篇文章 912人学习

全部文章（共10篇）

NC107617 poj3020 Antenna Placement

问题： n * m的矩阵，有一些障碍点，用12的骨牌覆盖所有非障碍点 (12骨牌可重叠，骨牌可越界，骨牌可延伸到障碍点) 问最少需要多少个。题解： • 尽量用一个骨牌覆盖两个格子，覆盖不了了再重叠使用骨牌• 用和上一个题一样的方式求一个最大匹配，那么就有（2 * 最大匹配）个点已经被覆盖了• 剩...

二分图匹配 **

2021-01-14

0 584

NC51272 棋盘覆盖

题目：给出一张n×n(n≤100) 的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。题解：先进行黑白染色，相邻的两个黑白就是一个骨牌，又因为一个格子不能放多个骨牌，所以相当于找每个格子的搭档（搭档即为相邻的点），使得搭档的数量足够多裸的二分图最大匹配代码：

二分图匹配 ***

2021-01-14

0 779

二分图匹配(二)

@[toc] 例题： NC20483 [ZJOI2009]假期的宿舍题目描述：学校放假了 · · · · · · 有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直...

二分图匹配题目集h

2021-01-13

0 688

NC107638 poj3041 Asteroids

题目描述：网格图中有若干个陨石，每次发射武器可以打掉某一行或某一列的所有陨石，求打完所有陨石的最少次数题解：首先，贪心的打星球最多的行/列有反例，如： 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 正解：我们把行和列抽象为点，把陨石抽象为边，即当（x,y）有一个陨石的...

二分图匹配匈牙利算法

2020-12-16

0 608

NC51316 Going Home

题目描述： n 个小人回到 n 间房子，要求一对一，告诉每个人的位置和每个房子的位置，问n个人移动的总距离最少是多少题解：最小权值匹配模板我们分别记录人和房，然后人与房连边并记录边权将所有边权值取相反数，然后跑一遍最优权值匹配模板详细看代码，仔细看看怎么构造图代码： #include<i...

二分图匹配最优匹配

2020-12-16

2 545

NC20483 [ZJOI2009]假期的宿舍

题目描述：学校放假了 · · · · · · 有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 B ...

二分图匹配匈牙利算法 **

2020-12-15

2 602

[ZJOI2007]矩阵游戏

来源：牛客网：题目描述小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）列交换操作：选...

二分图匹配

2020-09-22

0 1168

【每日一题】8月14日题目精讲 [SCOI2010]游戏

来源：牛客网：时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示...

二分图匹配

2020-08-30

0 601

【每日一题】7月9日题目 Color

来源：牛客网：时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 131072K，其他语言262144K Special Judge, 64bit IO Format: %lld @[toc] 题目描述给一个没有重边的二分图, 要求给边染色. 有公共点的边不能同色. 问最少用多少种...

二分图匹配匈牙利算法

2020-07-11

0 540

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

@[toc] 二分图：二分图是一个无向图，点集分成子集X和Y，图中每一条边都是一边在X一边在Y当且仅当无向图G的每一个回路次数都是偶数时（包括0），G就是一个二分图匹配介绍完二分图后我们看看匹配匹配：如果任意两个边的端点都不相同，我们就称之为匹配。匹配是边的集合最大匹配：所含匹配边数最多的匹配...

二分图匹配匈牙利算法

2020-07-11

0 595