| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 9/12 | Ø | Ø | Ø | Ø | Ø | Ø | Ø | . | . | Ø | . | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
2021 杭电多校 7 题解
| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 11/12 | Ø | . | O | O | O | O | O | O | O | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
从匈牙利算法到带权带花树——详解对偶问题在图匹配上的应用
引入
前些天看到了一个比较有趣的题目，需要用到一般图最大权匹配。可是我只会二分图最大匹配，甚至不会 KM 和带花树的原理，于是就进行了一个资料的搜，顺便增长一下板子库。然而——
对一般图最大权匹配，网上现成高质量资料较少。
苦于资料杂乱、且无论正确性还是代码具体实现都没有一个清晰的全流程教程，在吸取众长、奋斗三天后，终于通过了 UOJ 上的模板题。
这篇博客主要目的在于，梳理整个流程（包含代码实现）中应用的原理和使用的技巧。一般图最大权匹配主要通过下面四个问题逐步转化：
- 二分图最大匹配
- 一般图最大匹配
- 二分图最大权匹配
- 一般图最大权匹配
本文主要描述，如何通过解决前三个问题的思路，解决第四个更为复杂的问题。本文的前置知识只有匈牙利算法。
2019 Petrozavodsk Winter Camp, Yandex Cup 题解
| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 8/10 | O | Ø | O | Ø | . | Ø | . | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
2019-2020 Winter Petrozavodsk Camp, Day 8 Almost Algorithmic Contest 题解
| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 9/12 | Ø | Ø | O | . | O | O | O | O | O | . | . | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
2021 CCPC网络赛 题解
| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 10/13 | O | O | . | . | Ø | O | O | Ø | O | Ø | O | O | . |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
2021 牛客多校 10 题解
| Solved | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 11/12 | O | . | Ø | Ø | Ø | O | Ø | O | Ø | O | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
2021 牛客多校 3 题解
| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 9/10 | Ø | O | O | Ø | O | O | Ø | . | Ø | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest 题解
| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 11/12 | O | . | Ø | Ø | Ø | O | Ø | Ø | Ø | Ø | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
2021 牛客多校 2 题解
| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 12/12 | Ø | Ø | O | O | Ø | O | Ø | Ø | O | Ø | O | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
从分式第 n 项到线性递推——bostan-mori 算法的扩展应用
本文是在洛谷博客、博客园同时发布的P4723 【模板】常系数齐次线性递推题解。 介绍一个常数小还极其好写的科技：bostan-mori 算法。 不需要任何矩阵知识，前置知识：多项式乘法 波斯坦-茉莉算 ...
2020.3.4 OO研讨课 - 正则表达式和作业的一些碎碎念 提纲
（以下内容仅是提纲，其中的标题包含关系不代表内容包含关系，具体见讲述） 正则表达式正则表达式的本质 DFA(Deterministic Finite Automaton)，确定有限状态自动机 我们 ...
2017-2018 ACM-ICPC, Central Europe Regional Contest (CERC 17) 题解
| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 10/12 | O | Ø | . | Ø | . | O | O | O | Ø | O | Ø | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
2017 CCPC Hangzhou Contest 题解
| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 10/12 | O | O | O | O | O | ! | O | . | Ø | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
2019 ICPC Asia Shanghai Regional Contest 题解
| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 0/11 | . | . | . | . | . | . | . | . | . | . |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
2020 CCPC Wannafly camp day7 题解
| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 11/12 | O | Ø | O | . | O | O | O | O | Ø | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
2020 CCPC Wannafly camp day6 题解
| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M | N |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 13/14 | O | . | O | O | Ø | O | O | O | O | O | O | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet