月份:2019年4月

篇文章

B 酱的无向图 题解
[mdx_warning]本题目有版权,禁止复制[/mdx_warning] 题目描述 B 酱有$n$个节点的无向图,初始时图中没有边。他依次向图中加入了$m$条无向边,并询问你加入每条边后图中桥的个数是多少。被删除后能使图中连通块个数增加的边就称为桥。注意图中可能会出现重边及负环。 输入格式 输入第一行为三个正整数$n,m, p, p $的含义将…
10152. 「一本通 5.1 练习 3」矩阵取数游戏
题意 帅帅经常和同学玩一个矩阵取数游戏: 对于给定的 $n\times m$ 的矩阵,矩阵中每个元素 $a_{ij}$ 均为非负整数。游戏规则如下: 1. 每次取数时必须从每行各取走一个元素,共 $n$ 个,$m$ 次取完所有元素。 2. 每次取走的各个元素只能是该元素所在行行首或行尾。 3. 每次取数都有一个的分值,为每行取数得分之和,每行取数得…
EK (Edmond-Karp) 算法 学习笔记
什么是EK算法 EK (Edmond-Karp) 算法,说白了就是求最大流/费用流之类的问题的算法。 什么是最大流 定义 带权的有向图$G=(V,E)$,满足以下条件,则称为网络流图$(flow network)$: 仅有一个入度为$0$的顶点$s$,称$s$为源点。仅有一个出度为$0$的顶点$t$,称$t$为汇点。每条边的权值都为非负数,称为该边…