louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共3篇）

题解 | 算法竞赛进阶指南 Machine Schedule

思路很裸的二分图最小点覆盖题.首先,因为最开始都处于0模式,那么或的边都可以删去.然后因为最优情况下每种模式最多只转换一次,可以把转换过这种模式看作选择这种模式所代表的的点,而可以看作一条边.的模式是左部图,的模式是右部图.很明显,题目转换成这样一个问题:选择最少的点,使所有边都能覆盖到.这就是经...

二分图最大匹配二分图最小点覆盖

2019-08-24

0 495

题解 | 算法竞赛进阶指南棋盘覆盖

思路放置多米诺骨牌可以看作与或或或匹配的过程.因为与,奇偶性不同,可以分成一个二分图.这样就变成一个二分图匹配问题,能匹配且都不是障碍的两个点之间连边,直接跑匈牙利即可. 代码 #include<bits/stdc++.h> using namespace std; #define i...

二分图最大匹配

2019-08-24

0 561

题解 | 算法竞赛进阶指南車的放置

思路因为每一行只能有一个車,每一列也只能有一个車.因此把每一行当做一个节点,每一列当做一个节点,若行列能放棋子,行节点向列节点连边,这样就是一个二分图最大匹配问题.跑一遍匈牙利算法即可. 代码 #include<bits/stdc++.h> using namespace std; #...

二分图最大匹配

2019-08-23

0 622