Charlesss

ACM_二分图

ACM_RMQ(2) ACM_二分(5) ACM_前缀和(1) ACM_动态规划(18) ACM_干货(6) ACM_并查集(3) ACM_拓扑排序(2) ACM_搜索(24) ACM_最短路(14) ACM_树(1) ACM_树状数组(2) ACM_生成树(8) ACM_线段树(3) ACM_覆盖问题(2) ACM_连通图(2) CodeForces(131) 未归档(172) 第九届蓝桥杯(2) 算法(3) 补题补题补题(55) 题解(3)

/ 注册

全部文章 / ACM_二分图（共8篇）

POJ 2112 Optimal Milking(Floyd+二分+二分图多重匹配)

题目链接：http://poj.org/problem?id=2112 题意是有k台挤奶机，c头奶牛，每台挤奶机最多可以给m奶头牛挤奶，1--k是挤奶机的编号，k+1--k+c是奶牛的编号，然后输入一个邻接矩阵，表示它们任意两点间的距离，问这些奶牛去挤奶机的过程中，跑的最远的一...

2018-11-30

0 531

HDU 1669 -- POJ 2289 Jamie's Contact Groups(二分+二分图多重匹配)

题目链接(POJ)：http://poj.org/problem?id=2289 题目链接(HDU)：http://acm.hdu.edu.cn/showproblem.php?pid=1669 题意是Jamie有n个联系人，他现在要把这些人都分成组，现在已知每个人的可以分的...

2018-11-28

0 486

POJ 2594 Treasure Exploration(最小路径覆盖+Floyd)

题目链接：http://poj.org/problem?id=2594 题意是有n个点，m条单向边，然后在边上放机器人，问最少放多少个机器人能遍历到所有的点。看似是一道裸的最小路径覆盖问题，但是会有一种单向边相交的情况看下图 ...

2018-11-27

0 540

POJ 3020 Antenna Placement(二分图最小边覆盖)

题目链接：http://poj.org/problem?id=3020 题意是有一个n*m的地图，图中'*'表示城市，现在要给每个城市覆盖无线，需要安装基站，每个基站最多只能覆盖相邻的两个城市，也就是1*2或者2*1的大小，问最少需要安装多少个基站。正解就是去...

2018-11-27

0 598

HDU 2389 Rain on your Parade(二分图最大匹配--Hopcroft-Karp算法)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2389 题意是天马上就要下雨了，然后有n个人，m把伞，然后分别给出人的坐标和他们跑的速度，以及伞的坐标，然后问在t时间内，最多能有多少人拿到伞。题目读懂的话，就很容...

2018-11-26

0 758

HDU 4185 Oil Skimming(思维+二分图最大匹配数)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4185 题意是输入n*n的地图，然后问最多有多少个1*2或者2*1的'#'。思路就是用二分图，将相邻的'#'连一条边，然后在n*n的图内跑一个最大匹配数。难就难在如...

2018-11-08

0 530

HDU 2444 The Accomodation of Students(二分图判断+最大匹配数)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2444 题意是有n个人，m个配对，问能不能根据m个将这些人分成两个集合，且集合中的任意两人没有配对，其实这也就是二分图的定义。思路就是首先我们要用染色法判断一下这个图...

2018-11-08

0 508

Wannafly挑战赛27 B- 紫魔法师(二分图判断)

题目链接：https://ac.nowcoder.com/acm/contest/215/B 对于这道题我们要先读懂题意，说的是给了一个仙人掌形状的图...想象一下其实就是二分图，然后我们画个图就很容易找出规律，如果存在奇数的环就需要至少三个颜色，否则就是二分图的着色问题了。所...

2018-11-02

0 513