标签 - 最大流

? 解题记录 ? ? 网络流 ? ? 最大流 ?    2021-01-27 11:14:26    1541    0    0
链接标题 复习最小路径覆盖 最小路径覆盖是指对于给定的DAG,用最少的路径将其所有点覆盖,路径不相交。最小路径覆盖建图如下: 变式1:最小链覆盖 用最少的路径将其所有点覆盖,路径可以相交 做法:使用floyd传递闭包重连边,然后进行最小路径覆盖 变式2:最长反链 指选择最多的点,使得两两之间不能互相到达 做法:对偶问题:最长反链等于最小链覆盖 本题中发现球是依次加入的,如果有两个球和为完全平方数那么小的向大的连接单向边,一个柱子就相当于一条路径。那么可以知道K" role="presentation" style="position: relative;"&
? 解题记录 ? ? Topcoder ? ? 二分答案 ? ? 最大流 ? ? 动态规划 ?    2019-02-19 15:07:22    314    0    0
Easy FightMonsterDiv1 题意:你要打个怪,有HP" role="presentation" style="position: relative;">HPHPHP点血。你一开始的攻击力是ATK(/s)" role="presentation" style="position: relative;">ATK(/s)ATK(/s)ATK(/s),攻击力每1s" role="presentation" style="position: relative;">1s1s1s会增加原始攻击力ATK" role="presentation" style="positio
? 解题记录 ? ? Atcoder ? ? 贪心 ? ? 最大流 ?    2019-02-14 15:49:52    681    0    0
A Irreversible operation 签到题,直接for" role="presentation" style="position: relative;">forforfor一遍就好了 B Powers of two 题意:给n" role="presentation" style="position: relative;">nnn个数字,要两两配对凑成和为2i" role="presentation" style="position: relative;">2i2i2^i的数对,问最多凑多少个。 题解:感觉上排个序从大往小匹配卡不掉,也不会证
? 解题记录 ? ? 洛谷 ? ? 二分答案 ? ? 网络流 ? ? 最大流 ?    2018-07-15 11:22:03    387    0    0
题意翻译描述 掷骰子是一种双人游戏,它的结果是完全随机的。最近它在整个Byteotia变得非常流行。在Byteotia的首都甚至有一个特别的掷骰子业余爱好者俱乐部。俱乐部的老主顾们花时间互相聊天并每隔一阵子就和一个随机选择的对手玩这他们最喜欢的游戏。一天中赢得最多游戏的人会得到“幸运者”头衔。有时晚上俱乐部很安静,只有很少的比赛。这是哪怕赢一场也能获得“幸运者”头衔的时间。 很久很久以前有一个很不走运的人,叫Byteasar,赢得了这个光荣的头衔。他被深深地震惊了以至于完全忘了他已经赢了多少场。现在他想知道他有多幸运,以及幸运之神是否最终会向他微笑——也许他的运气会变好?他确切地知道在那个幸运
? 解题记录 ? ? 洛谷 ? ? 最大流 ? ? 网络流 ?    2018-01-26 20:02:06    484    0    0
题目描述如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。 输入输出格式输入格式:   第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。 接下来M行每行包含三个正整数ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)   输出格式:   一行,包含一个正整数,即为该网络的最大流。   输入输出样例输入样例#1: 复制4 5 4 3 4 2 30 4 3 20 2 3 2
? 洛谷 ? ? 解题记录 ? ? 最大流 ? ? 网络流 ?    2017-11-17 20:14:28    666    0    0
题目描述农夫约翰的奶牛们喜欢通过电邮保持联系,于是她们建立了一个奶牛电脑网络,以便互相交流。这些机器用如下的方式发送电邮:如果存在一个由c台电脑组成的序列a1,a2,...,a(c),且a1与a2相连,a2与a3相连,等等,那么电脑a1和a(c)就可以互发电邮。 很不幸,有时候奶牛会不小心踩到电脑上,农夫约翰的车也可能碾过电脑,这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了,于是与这台电脑相关的连接也就不可用了。 有两头奶牛就想:如果我们两个不能互发电邮,至少需要坏掉多少台电脑呢?请编写一个程序为她们计算这个最小值。 以如下网络为例: 1* / 3 - 2* 这张图画的是有2条连接的
? 解题记录 ? ? HDU ? ? 最大流 ? ? 补档计划第一期 ? ? 网络流 ?    2017-10-01 13:58:27    542    1    0
  给你一个m*n的格子的棋盘,每个格子里面有一个非负数。 从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取数所在的2个格子不能相邻,并且取出的数的和最大。 Input 包括多个测试实例,每个测试实例包括2整数m,n和m*n个非负数(m<=50,n<=50) Output 对于每个测试实例,输出可能取得的最大的和 Sample Input 3 3 75 15 21  75 15 28  34 70 5​Sample Output 188​​