19-大数据一班-杨文冠

题解

学习(23) 未归档(1) 练习(1)

/ 注册

全部文章 / 题解（共4篇）

题解 | #校庆#

题解拍照从1∼n{1\sim n}1∼n和从n∼1{n\sim 1}n∼1分别跑一遍最长上升子序列，枚举最高的人i{i}i时，计算1∼i{1\sim i}1∼i和n∼i{n\sim i}n∼i之和，取和最大的i{i}i。（枚举最高的人i{i}i时要保证i{i}i被选到，所以要分别从前和从后跑一遍...

dp 最长上升子序列 ac自动机最大流最小割线段树二分 KM 括号匹配

2021-11-23

2 486

【模板】最大流加强版 / 预流推进来自专栏

给定 n 个点，m 条有向边，给定每条边的容量，求从点 s 到点 t 的最大流。 DinicDinicDinic算法复杂度上界为n2mn^2mn2m，可以优化到nmlogCnmlogCnmlogC ，CCC是最大的流量，代补。 HLPPHLPPHLPP算法复杂度上界为n2mn^2 \sqrt{m} ...

HLPP 最大流

2021-05-09

2 767

Cable TV Network 来自专栏

思路：无向图不连通则必有两个点不连通，枚举两个点，求在剩下的个节点中最少去掉多少个点，可以使和不连通，在每次枚举的结果中取最小值就是这题的答案。拆点的两种方式：1.入点和出点分别是和，需要知道有多少个点2.入点和出点分别是和点的出边到的入边的最小割就是需要去掉的点，枚举完后把反向边的容量加回去就可...

最大流网络流最小割

2021-05-05

1 678

舞动的夜晚来自专栏

思路：用网络流跑二分图的最大匹配，先将H公司第个人的编号变为，然后表示公司和公司的两个人有关系,待匹配。残余网络中非匹配边为从左部到右部的有向边，的边权为，匹配边为从右部到左部的有向边，边权为。非匹配边：，表示边的容量匹配边：因为要求不可行的边的数量，即不是可行边和必须边的边；先跑一遍最大匹配最大匹...

最大流

2021-05-05

1 493