本文主要讲建图方法,定义和证明内容较少。 正好网络流二十四题做完了整理下。 目录 网络流模型 最大流最小割 最小割树 平面图最小割 费用流 SSP 算法 有负圈的费用流 上下界建模 无源汇上下界可行流 有源汇上下界...
APIO2023 赛博乐园
“并没有 不一样 为何感到悲伤” —— 《尘降》 分析 首先把图反着跑,这样总通行时间除以 222 就变成了后续时间都除以 222,当前总通过时间为 000 就变成了后续时间都为 000。 然后把一个点拆开成 K+2K+2K+2...
ABC241G 题解
分析 枚举第一名,假设以后的比赛该名玩家都获胜,然后判定是否合法。 数据范围很网络流,考虑最大流,流量代表得分,然后是建图: 源点和每场比赛连容量为 111 的边 比赛如果有胜负就向胜者连边,否则就向参与比赛的两个人连边 设第一名...
APIO2023 线上游记
“请告诉我为何心不停的跳动 这颗心究竟装着什么” —— 《人偶之梦》 分析 注意到 pi<pjp_i<p_jpi<pj 则 ci≤cjc_i\leq c_jci≤cj,存在偏序关系。 一个贪心的想法是,按照...
APIO2023 线上游记
day-? 报名被报成线上了,寄寄寄。 day-? P 和我的年龄给了我可能今年唯一能看的成绩。 day 0 麦会炸,是那种嘶吼声的回音的感觉。 字符串,感觉自己没学过了。 直播能很好看到旷课人数,很震撼,签到更震撼。 同时知道...
ABC299G 题解
“まだ動くまだ進む 物語の上を泳げ” —— 《スイマー》 分析 维护一个栈,每次加入一个值。 如果栈顶在之后也会出现并且比加入的值大就弹出。 这样使得每个值尽可能放在前面。 粗略的证明一下。假设有两个序列 A,BA,BA,B,AAA...
P4200 题解
“遥か月を目指した 今日の空は 彼方西に流れた もう届かないや 届かないや”——《回る空うさぎ》 分析 首先对于每个坐标开一颗平衡树,要维护的东西需要全局取 max,但是自己不能取。 士气值和团结值在一个点没加进去之前是好算的,直接...
ABC295G 题解
“「あるべき人間の姿へ」 「正しい人間の姿へ」 そう思えばなんだか 人間全てが汚く思えてくるな”—— 《不可解》 题意简述 给定一张点数为 NNN 的有向图,初始 pi(1≤pi≤i,1≤i<N)p_i(1\leq p_i \...
圆方树
模拟赛考到了,正好写一下。 简介 圆方树是一种将图变成树的方法,解决一些路径连通性相关的东西或者是仙人掌。 描述 前置知识:点双连通分量。以下不考虑孤立点。 在圆方树中,原来的点为圆点,点双为方点。每个点双内部是一个菊花图 [1]...
ABC279F 并查集题解
“我仍然在无人问津的阴雨霉湿之地” —— 《世末歌者》 题意 高橋君有 NNN 瓶糖水,青木君有 MMM 瓶糖水。 高橋君的第 iii 瓶糖水有 AiA_iAi 份糖 BiB_iBi 份水。 青木君的第 iii 瓶糖水有 C...