KetchupZ
KetchupZ
全部文章
# 网络流/最...
# 01_容斥定理(2)
# AC自动机/Manacher(8)
# color coding k-th近似算法(1)
# KMP(7)
# LCA(3)
# Prufer序列/无向图三元环计数(3)
# 凸包/旋转卡壳(2)
# 割点/割边/强连通分量(4)
# 区间DP(1)
# 单调队列/单调栈(6)
# 压缩算法(1)
# 回文自动机(3)
# 字典树(7)
# 字符串Hash(1)
# 实战项目(6)
# 并查集(2)
# 扩展欧几里得/中国剩余定理(3)
# 排序算法(5)
# 数位DP(8)
# 数论杂项(2)
# 最小生成树(3)
# 最小费用流(5)
# 最短路径/差分约束/最长路(12)
# 朴素DP(1)
# 树形DP(4)
# 树状数组(11)
# 概率DP(3)
# 欧拉函数/素数(2)
# 欧拉路径/其他(1)
# 欧拉降幂(1)
# 状压DP(8)
# 线段树(2)
# 背包问题(6)
# 莫比乌斯反演(2)
# 语法/函数/部分骚操作(15)
++++++++几何数学++++++++(2)
++++++++数论++++++++(1)
+++++图论++++++++(2)
+++++字符串++++++++(1)
+++++数据结构++++++++(1)
+++++组合数学++++++++(7)
100场比赛计划(7)
cdq分治(1)
Codeforce(12)
专项之C/C++(13)
专项之Java(11)
专项之Liunx(1)
专项之sql(6)
专项之计算机网络(2)
其他题目/思维/贪心(42)
暴力/尺取/二分/三分(10)
未归档(11)
比赛历程(1)
比赛技巧(5)
深搜/广搜(5)
珂朵莉树/老司机树(1)
归档
标签
去牛客网
登录
/
注册
KetchupZ的博客
全部文章
/ # 网络流/最小割/二分图匹配
(共10篇)
最小割总结
<center> 最小割 </center> 什么是最小割? 割掉网络图的一些边,使得之后的顶点分为两部分,即S可以到达的顶点集合和可以到达T的顶点集合,每个边割开都有会产生一个费用;而最小割就是我们使顶点分为两部分的费用和最小的割法。 且我们已经证明最小割等...
2019-04-02
0
485
网络流总结
网络流我习惯采用EK算法 思想: 每次从残留网络找出一条增广路,并且沿着这条路增广即可,直至没有增广路 关于网络流的用处: 网络流就像水流一样,求最大的水流速率,很多问题可以转化为网络流模型来解决 二分图匹配( 最少边覆盖) 网络流的做题经验: 求最大消...
2019-04-02
0
786
B - Evacuation(二分图最大匹配,网络流,元组建图)
B - Evacuation POJ - 3057 题意: 墙壁“X”,空区域(都是人)“.”, 门“D”。 人向门移动通过时视为逃脱,门每秒能出去一个人,人可以上下左右移动,墙阻止移动。 求最优移动方案下,最后一个人逃脱的最短时间。如果有人无法安全逃脱(比如被墙围困住),则输出“i...
2019-04-02
0
489
C - Dual Core CPU(最小割)
C - Dual Core CPU(最小割,ISAP实现) POJ - 3469 题意: 一个双核CPU上运行N个模块,每个模块在两个核上运行的费用分别为Ai和Bi。 同时,有M对模块需要进行数据交换,如果这两个模块不在同一个核上运行需要额外花费。 求运行N个模块的最小费用。 分析...
2019-04-02
0
499
M - Escape HDU - 3605 (最大流,状态压缩)
题意: 有n个人,m个星球,下面有n行,每行有m个数字,0或1。如果第 i 行第k 个数字为0代表第i 个人不适合生活在星球k,否则适合生活在星球k。每个星球有可以容纳的人数,能否将所有人都转移星球。 分析: 最大流,普通的建图很容易想出来,但是n是个10w左右的数...
最大流
2019-03-29
0
586
UVA - 10480(最小割路径)
UVA - 10480 题意: 给你一个网络图,开始时候有 n n n, ...
2019-03-29
0
493
G - Island Transport HDU - 4280
G - Island Transport HDU - 4280 In the vast waters far far away, there are many islands. People are living on the islands, and all the transport amo...
2019-03-23
0
499
C - A Plug for UNIX(网络流)
C - A Plug for UNIXPOJ - 1087 题意: 给你一些插头,和插座。插头和插座分别有不同的型号,只有相同的型号才能配成一对。现在有k个转换器,每种转换器有无限个,但不一定有所有的转换器型号,转换器的作用是:将一个插头转换成另一个插头。现在求你最少有多少个插头不能插到插...
2019-03-17
0
527
B - Dining POJ - 3281 (网络流 Ek算法实现)
题意: 有f 个食物和 d个饮料,现在有n头牛,每头牛有喜欢的食物和饮料。每头牛只吃自己喜欢的饮料和食物,且食物和饮料各吃一个才算满足,问最多能满足多少个牛? 分析: 这是挑战书上的例题,花式建图,下面的图中,f是食物,d是饮料。 令s到f的权值为1...
2019-03-16
0
540
ACM Computer Factory(网络流 POJ 3436,这可是我第一次写网络流)
ACM Computer Factory(网络流 POJ 3436,这可是我第一次写网络流) 题意: 有n台机器,每台机器有一个输入规则和输出规则 和一个最大生产速率,且每个输出和输出的属性有q个。 且对于机器的输入规则状态0代表没有,1代表必须有,2代表无所谓,输出规则的状态只有0 和1。...
2019-03-16
0
438