2020-2021:teams:manespace:zjoi矩阵游戏
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:zjoi矩阵游戏 [2020/05/31 18:27] iuiou 创建 |
2020-2021:teams:manespace:zjoi矩阵游戏 [2020/06/04 11:40] (当前版本) intouchables [1] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== ZJOI 矩阵游戏 ====== | + | ====== ZJOI 矩阵游戏(by iuiou) ====== |
| =====题意===== | =====题意===== | ||
| 行 15: | 行 15: | ||
| ===== 放这题有什么意义呢 ===== | ===== 放这题有什么意义呢 ===== | ||
| - | <del>当然是因为实在没啥好放的了</del>，这是非常简单的二分图和网络流建模的问题，适合刚学二分图批配或者网络流的新手，<del>比如我</del>初步体会一下建模的艺术。 | + | <del>当然是因为实在没啥好放的了</del>，这是非常简单的二分图和网络流建模的问题，适合刚学二分图匹配或者网络流的新手，<del>比如我</del>，初步体会一下建模的艺术。 |
| ===== 题解 ===== | ===== 题解 ===== | ||
| 行 25: | 行 25: | ||
| ==== 1 ==== | ==== 1 ==== | ||
| - | 匈牙利算法： 本质上是一个递归找对应得方法，基于一些比较复杂得图论得定理，这里不做详细描述(<del>其实我不会</del>)，在本题中，如果一次找批配失败找不到则宣告失败，应为注定无法完全匹配。 | + | 匈牙利算法： 本质上是一个递归找对应得方法，基于一些比较复杂得图论得定理，这里不做详细描述(<del>其实我不会</del>)，在本题中，如果一次找匹配失败找不到则宣告失败，因为注定无法完全匹配。 |
| ==== 2 ==== | ==== 2 ==== | ||
| - | 网络流：建立虚点，源点和汇点，汇点链接右端点，源点链接左端点，跑ek或者dinic最大流。由于dinic最大流得特点，这里分层最多也只能分4层，而且还有一些玄学原因，所以这里跑dinic算法复杂度是相当优秀的，远远高于普通最大流和匈牙利算法。**dinic果然赛高！！！** | + | 网络流：建立虚点，源点和汇点，汇点链接右端点，源点链接左端点，跑$ek$或者$dinic$最大流。由于$dinic$最大流得特点，这里分层最多也只能分4层，而且还有一些玄学原因，所以这里跑$dinic$算法复杂度是相当优秀的,似乎是$O(\sqrt n m)$，远远高于普通最大流和匈牙利算法。**dinic果然赛高！！！** |
| ===== 代码 ===== | ===== 代码 ===== | ||
2020-2021/teams/manespace/zjoi矩阵游戏.1590920859.txt.gz · 最后更改: 2020/05/31 18:27 由 iuiou
