网络流 练习记录

作者: wjyyy 分类: 网络流,记录 发布时间: 2019-01-10 19:41

点击量:223

与LCT练习记录不同的是,这篇文章可能加入todo-list。

发现了宝贝

hihocoder里面的hiho一下在16年的时候总结了一些网络流的知识,以题目/模板的形式展现了出来,可以看看。

模板

洛谷 P3376 【模板】网络最大流

标准模板,可以检验出各种错误。

2018年8月之前都喜欢用EK写,直到看到了Dinic的板子——好短啊……

题目链接 代码

洛谷 P3381 【模板】最小费用最大流

也是费用流模板。写spfa时不开O2能接近1000ms。真理:人丑常数大

题目链接 代码

洛谷 P3386 【模板】二分图匹配

二分图匹配,可以直接用最大流做,只需要一个超级源点和超级汇点。超级源点到每个左侧点都连一条边;每个右侧点到超级汇点都连一条边。每条有向边容量为1。

这里不加特判

if(flow==0)
    break;

会TLE,而模板3376就不会有这个问题。以后还是加上吧。

题目链接 代码

基础题

洛谷 P1231 教辅的组成

是一道“三分图”。实际上是把匹配转化为了三组元素,和二分图匹配的做法几乎一致,要读懂题目每个参量描述的是什么意思。

注意书要拆点,以保证所有的只被包含在一套教辅里面。

题目链接 代码

网络流24题

进度从2019年1月10日开始统计。期望在省选前完成。

来源/题号/题目顺序:洛谷

有上下界的网络流

sgu 194 Reactor Cooling (无源汇)

(ZOJ也有这个题)

裸的上下界网络流了。

题解写在这里

题目链接 代码

poj 2396 Budget (有源汇)

这个题需要拆点。每个点多出来的那条边表示这个点的权值。

给每个源点和汇点连上相应流量的附加边,然后从\(S\)到\(T\)跑最大流就可以了。

题目链接 题解

洛谷 P4043 [AHOI2014/JSOI2014]支线剧情

这个题只有下界,但是需要计算费用。

一开始把题目看错了以为每个点都要经过一次,还变麻烦了

因为上下界网络流的特殊性,附加边已经帮原来的边跑掉了下界,因此计算答案时要额外加上每一条边的边权。

题目链接 题解

类似的题目(todo-list

每个点都要经过一次(这就是上面的题看错的解法)。

据说是最小流?也是DAG版的最小路径覆盖,每个边至少跑一次。

建立源点,连到所有入度为\(0\)的点;建立汇点,所有出度为\(0(m=0)\)的点连一条边到汇点。

然后针对这个有源汇的图(源汇无限流量)跑一下下界为\(1\)的可行流就可以了。

  • bzoj 3698 XWW的难题 (权限题)

todo-list

说点什么

avatar
  Subscribe  
提醒
/* */