网络流简述
本文将从简要介绍网络流的定义，最大流和最小割之间的关系，并使用C++实现EK算法和Dinic算法。本文还会简单地介绍费用流。部分定义和论证过程可能不够严谨，仅助于理解，严谨的定义和证明过程请在参考资料中查阅。 网络流相关定义 例子 我们在讨论定义之前，先看一个例子。 假设我们得到了一个城市的所有下水管道的数据，这份数据的表示方法为：以交叉水管口为节点（二叉口、三叉口…），以交叉口之间的边为链接节点之间的边，建立一个有向图。每段水管有各自的最大水流量，假设这个城市只有一个出水口排水到城市外。你想知道，在离你家最近的那个水管交叉口注水，注水的流量极大，足够长时间后那个出水口的流量是多少。 网络流定义 对于一个有向图G=(V,E)G=(V,E)G=(V,E)，有一个源点sss（source）和一个汇点ttt（sink），(s≠t)(s\not =...
测试
这是一级标题 这是二级标题 这是第一行 这是第二行 这是第三行 这是第四行 文字显示 这是粗体 这是斜体 这是下划线 ==这是高亮== 这是删除线 1*2*3*4*5 x^2^ y~1~ x^2^~1~ 无序列表 一 二 三 三1 三1（1） 退出反复按回车 有序列表 aaaaa bbbbb ddddd eeeee fffff ccccc 任务列表 [ ] [ ] 区块显示 代码显示 int a = 0 快速选中 ctrl+shift+ 代码块 12345678#include <iostream>using namespace std;int main(){ printf("Hello Markdown."); return 0;} 链接 www.baidu.com 这里 文内链接 脚注 文字[^1] [^1]:这是脚注...
