寒江陪烟火🔥
寒江陪烟火🔥
全部文章
二分匹配
acm相关(6)
dp(68)
RMQ(5)
STL(6)
主席树(2)
二分查找(2)
分治法(3)
划分树(1)
单调队列(2)
博弈(11)
字典树(3)
字符串处理(1)
学习(1)
并查集(4)
强联通分量(3)
归并排序(1)
拓扑排序(1)
搜索(1)
数论(8)
最小生成树(3)
最短路(5)
树状数组(7)
树链剖分(4)
欧拉回路(5)
简单模版(14)
简单题(24)
线段树(13)
网络流(6)
归档
标签
去牛客网
登录
/
注册
寒江陪烟火🔥的博客
全部文章
/ 二分匹配
(共23篇)
HDU1151 Air Raid(有向图最小路径覆盖)
题意: N个点M条边的有向图 意思就是问最小覆盖 思路: 有向图建单向边,然后匈牙利求最大匹配数 用N-最大匹配就可以了 /* *********************************************** Author :devil Created ...
2016-05-17
0
186
HDU1054 Strategic Game(二分匹配)
题意: 给你一个图,然后每个点被覆盖的时候,相邻的点也会被覆盖 求最小的数量使所有点被覆盖 思路: 学树形dp的时候做过这道题了,绝对比二分图快。。 现在刷二分图,n=1500,用匈牙利和HK算了下 先上匈牙利。。624ms /* ************************...
2016-05-17
0
219
POJ3020 Antenna Placement(最小边覆盖)
题意: 一个矩形中,有N个城市’*’,现在这n个城市都要覆盖无线,若放置一个基站,那么它至多可以覆盖相邻的两个城市。 问至少放置多少个基站才能使得所有的城市都覆盖无线? 思路: 给每个城市编号,建双向边,跑匈牙利,然后城市数量-匹配数/2就是答案 因为假设每个城市都要建基站,然后有多少个匹配...
2016-05-17
0
290
HDU4185 Oil Skimming(匈牙利)
题意: n*n的图 相邻两##可除去 问最多除去多少 奇偶建图,OK /* *********************************************** //Author :devil //Created Time :2016/5/12 14:48:...
2016-05-12
0
206
HDU2389 Rain on your Parade(HK模版)
题意: 在一个二维坐标系上有n个人和m把伞,每个人都有自己的移动速度, 问有多少人可以在s min内移动到不同的雨伞处(不允许两个人共用一把伞)。 思路: 由于nm太大(3000),匈牙利会超时,就用HK算法 整理了HK的模版 /* ************************...
2016-05-10
0
205
HDU2819 Swap(二分匹配+输出结果)
题意: 给一个n*n的01矩阵,问能否通过行列交换使得 主对角线上的数都为1 如果能输出交换的过程,如果不能输出-1 思路: 线性代数学过,行列交换都不改变矩阵的秩 三秩相等 如果能改变成主对角线上的数都为1 则原矩阵必为满秩 /* *********************...
2016-05-10
0
217
HDU1281 棋盘游戏(二分匹配+找必要的点)
题意: 给你一个n*m的地图和k个地图上可以放车的点 让你求出最多放多少个车和哪些点是必要的(没有它匹配数就会减少) 思路: 匈牙利求最大匹配,然后一个一个的删除匹配点进行匹配, 如果删除该点后匹配数减少,则这个点就是必要的 代码: 一开始用vector要记删除的点参数比较麻烦 ...
2016-05-10
0
266
HDU1083 Courses(二分匹配)
题意: p门课程n个学生,下面给出每门课程的学生数量和编号 问能否每门课选出课代表 每名学生只能担任一门课的课代表 思路: 裸的匈牙利算法,没什么好说的了 /* *********************************************** //Author ...
2016-05-10
0
208
HDU2444 二分图判断+最大匹配
题意: 给你n个点m条边的图,判断是否为二分图 如果不是输出No 如果是输出最大匹配 判断用交叉染色法(dfs简单bfs防暴) 最大匹配跑一边匈牙利算法 /* *********************************************** Author ...
2016-05-06
0
252
HDU1045 Fire Net(二分匹配)
题意: 给出一张n*n的图,图中'X'表示墙,'.'表示空地,可以放点同一条直线上只能有一个点,除非有墙隔开,问在给出的图中 最多能放置多少个点 思路: 4*4的图。。暴搜完全就可以了,不过是二分匹配专题就学了一发 把原图按行按列缩点,一行一列相邻的区域只能放一个 然后用行点和列点进行匹...
2016-05-05
0
186
首页
上一页
1
2
3
下一页
末页