/%E7%BD%91%E7%BB%9C%E6%B5%81%E5%B8%B8%E8%A7%81%E5%BB%BA%E6%A8%A1

网络流常见建模

本文主要讲建图方法,定义和证明内容较少。 正好网络流二十四题做完了整理下。 目录 网络流模型 最大流最小割 最小割树 平面图最小割 费用流 SSP 算法 有负圈的费用流 上下界建模 无源汇上下界可行流 有源汇上下界...

/APIO2023%20%E8%B5%9B%E5%8D%9A%E4%B9%90%E5%9B%AD

APIO2023 赛博乐园

“并没有 不一样 为何感到悲伤” —— 《尘降》 分析 首先把图反着跑,这样总通行时间除以 222 就变成了后续时间都除以 222,当前总通过时间为 000 就变成了后续时间都为 000。 然后把一个点拆开成 K+2K+2K+2...

/ABC241G%20%E9%A2%98%E8%A7%A3

ABC241G 题解

分析 枚举第一名,假设以后的比赛该名玩家都获胜,然后判定是否合法。 数据范围很网络流,考虑最大流,流量代表得分,然后是建图: 源点和每场比赛连容量为 111 的边 比赛如果有胜负就向胜者连边,否则就向参与比赛的两个人连边 设第一名...

/APIO2023%20%E7%BA%BF%E4%B8%8A%E6%B8%B8%E8%AE%B0

APIO2023 线上游记

“请告诉我为何心不停的跳动 这颗心究竟装着什么” —— 《人偶之梦》 分析 注意到 pi<pjp_i<p_jpi​<pj​ 则 ci≤cjc_i\leq c_jci​≤cj​,存在偏序关系。 一个贪心的想法是,按照...

/APIO2023%20%E7%BA%BF%E4%B8%8A%E6%B8%B8%E8%AE%B0

APIO2023 线上游记

day-? 报名被报成线上了,寄寄寄。 day-? P 和我的年龄给了我可能今年唯一能看的成绩。 day 0 麦会炸,是那种嘶吼声的回音的感觉。 字符串,感觉自己没学过了。 直播能很好看到旷课人数,很震撼,签到更震撼。 同时知道...

/ABC299G%20%E9%A2%98%E8%A7%A3

ABC299G 题解

“まだ動くまだ進む 物語の上を泳げ” —— 《スイマー》 分析 维护一个栈,每次加入一个值。 如果栈顶在之后也会出现并且比加入的值大就弹出。 这样使得每个值尽可能放在前面。 粗略的证明一下。假设有两个序列 A,BA,BA,B,AAA...

/P4200%20%E9%A2%98%E8%A7%A3

P4200 题解

“遥か月を目指した 今日の空は 彼方西に流れた もう届かないや 届かないや”——《回る空うさぎ》 分析 首先对于每个坐标开一颗平衡树,要维护的东西需要全局取 max,但是自己不能取。 士气值和团结值在一个点没加进去之前是好算的,直接...

/ABC295G%20%E9%A2%98%E8%A7%A3

ABC295G 题解

“「あるべき人間の姿へ」 「正しい人間の姿へ」 そう思えばなんだか 人間全てが汚く思えてくるな”—— 《不可解》 题意简述 给定一张点数为 NNN 的有向图,初始 pi(1≤pi≤i,1≤i<N)p_i(1\leq p_i \...

/%E5%9C%86%E6%96%B9%E6%A0%91

圆方树

模拟赛考到了,正好写一下。 简介 圆方树是一种将图变成树的方法,解决一些路径连通性相关的东西或者是仙人掌。 描述 前置知识:点双连通分量。以下不考虑孤立点。 在圆方树中,原来的点为圆点,点双为方点。每个点双内部是一个菊花图 [1]...