最近在学习数据结构和算法时，遇到了麻烦的问题。 那是网络流中的最大流算法，最初使用的是EK算法，最后随着数据的规模越来越大，为了解决所有问题，似乎都必须归结为Dinic算法
但是，发生了问题。 在网上看到的问题大部分都是直接上了主意，放了板子，就是这个，但是板子确实不太清楚。 现在科普一下，做链式前向星吧。 这是一种数据结构，出现在匡比模板上，第一个看到的雾水，后来才明白了这个东西的神秘
简而言之，链式前向星是用于存储图的数据结构。 在稀疏图中，二维阵列浪费了空间，这是以前使用二维阵列时遇到的问题。 链式前向星通过结构体排列和排列实现了我们的功能
class node{private int to； //终点保密下一步； //下一边private int volume； //边的容量专用流； //边的通信量公共int getto ({ return to； }publicvoidsetto(intto ) {this.to=to； }public int getNext () {return next； }publicvoidsetnext(intnext ) {this.next=next； }public int getVolume () {return volume； }publicvoidsetvolume(intvolume ) {this.volume=volume； }public int getFlow () {return flow； }publicvoidsetflow(intflow ) {this.flow=flow； }公共节点(int to，int next，int volume，int flow ) {super )； this.to=to； this.next=next； this.volume=volume； this.flow=flow； }我在这里遇到了第一个问题。 我还以为他们会记录边缘的起点、终点和容量、流量。 但是后来，我发现他不打算记录起点。 起点实际使用head[i]数组进行记录。 具体操作如下
//count=2； //map是结构体排列//uvw分别为起点、终点、容量publicstaticvoidaddnode(intu，int v，int w ) map[count]=newnode ) v、head[u]、w 出局； map [ count ]=新节点(u，head[v]，0，0 )； head[v]=count； 出局； }也就是说，在制作这一边时，我们会在结构体上记录边的终点和流量、容量，同时记录next，但head[u]=count可以巧妙地将起点和边关联起来，从某一点I的编号中找到以I为起点的边的信息但是，可能有聪明的伙伴。 你这样只能记住最后一边了吗？
但是，还留有手上的next域。 如果输入以I为起点的第二条边，则可以看到原始head[u]包含前一条边的下标。 此下标存储在第二条边的next域中，第二条边与第一边直接连接而不是起点。 最后得到的是链表数组，被认为在我们手中
上图为示意图。 黄色的线表示原来的边的结构，黑色的线表示使用链式前向星之后的记忆结构。 有了这个基础，下面的博客将开始组织最大流算法EK和Dinic