https://uoj.ac/submission/417401 没过 3、4 过了 5

两分钟之内就能将教练扔给你的题传到校内 UOJ 上是怎么回事呢？校内 UOJ 相信大家都很熟悉，但是两分钟之内就能将教练扔给你的题传到校内 UOJ 上是怎么回事呢，下面就让小编带大家一起了解吧。

UOJ Data Converter 可以将各种格式的数据转换成 UOJ 的格式，包括数据添加、文件名转换、子任务设置、添加样例、添加 std、生成 problem.conf 等一系列繁琐的工作，它都可以帮你完成。UOJ Data Converter 是使用 Qt 开发的，因此是跨平台的，不管你是喜欢使用 Windows 还是 Linux 都能愉快地使用它。有了 UOJ Data Converter，如果你手速够快，两分钟之内将教练扔给你的题传到校内 UOJ 上也就不是难事了。

大家可能会觉得很奇怪，这样一个神奇的软件，为什么我之前从来没有听说过呢？小编也非常惊讶，但据小编了解，有一位 OIer 最近经常被教练要求把题传到校内 OJ 上，并且这位 OIer 有一定的 Qt 开发经验，本着“能够花十个小时自动化的事，就一定不要花十分钟去做”的信念，他就花了三天时间把 UOJ Data Converter 写出来了。

可是，这样一个软件，如果放在 GitHub 上，大家又能怎么下载呢？其实它不止放在了 GitHub 上，还在 Gitee 上有镜像。

以上就是两分钟之内就能将教练扔给你的题传到校内 UOJ 上的全部内容了，大家有什么想法呢，欢迎在评论区告诉小编一起讨论哦！

Competitive Companion 是一个自动获取 OJ 题目 TL/ML/样例 的浏览器扩展，为了解析这些内容，需要统一的格式。

由于 ，UOJ 不能自动显示 TL 和 ML，于是 UOJ 上就有了千奇百怪的 TL ML 格式。下面的正则表达式描述了大多数题目的格式：

时间限制(?:</strong>)?(?:：|:)(?:</strong>)? ?\$.*?([1-9][0-9]*).*?\$
(?:空间|内存)限制(?:</strong>)?(?:：|:)(?:</strong>)? ?\$.*?([1-9][0-9]*).*?(M|G)B.*?\$

但是，依然有以下题目不符合该格式：

• 317
• 349
• 395
• 411
• 412
• 413
• 451
• 452
• 457
• 459
• 472
• 473
• 475
• 476
• 477
• 481
• 482
• 483
• 484
• 485
• 486
• 494

（里面可能混了一些无法修正的，我是爬虫之后手动把提答什么的删掉的。）

如果再扩展正则表达式就太复杂了，希望管理们能够将这些题目的时空限制规范化一下 /kel（其实 LaTeX 格式什么的再改改正则表达式也还行，像有的题目时限有 删除线 就比较难顶了 /fad）

See also: jmerle/competitive-companion#75

我写的消圈算法好像和通常意义上的还不太一样，据我了解，最原始的消圈算法是每次求最大流再在残量网络上消负环，然而我是先通过加一条 t 到 s 容量足够大费用足够小的边把问题转化成无源汇最小费用流（或者叫最小费用循环流），然后直接消负环。消的顺序是依次消掉包含每个点的所有负环。

这样应该是伪多项式且可以在当前数据范围内叉掉的吧（

提交：http://uoj.ac/submission/371127

加了点随机的提交：http://uoj.ac/submission/371132

求 hack /kel （或者指出在数据范围内叉不掉）

最近学了下基于 Capacity Scaling 的弱多项式复杂度最小费用流算法，写了篇博客。

感觉相关资料比较少，我自己只搜到了论文，还是 在 CF 老哥的帮助下 才找到了合适的学习资料..

博客传送门，欢迎找 bug~

P.S. 论文和 notes 中都提到了最小费用流的线性规划形式的对偶问题，还证明了几个相关的定理，但感觉算法流程中并没有用到，不知道是不是我哪没有注意，如果有问题还请指出。