Loading... # 问题 将下面这篇文章中问题的条件修改为流量可以被分割，也就是最大流模型。 <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.co1in.me/archives/31/" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.co1in.me/usr/themes/handsome/assets/img/sj/2.jpg);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">用Dijkstra寻找最大带宽路径</p> <div class="inster-summary text-muted"> 问题一个计算机网络，计算机为节点，连接他们的线为无向边，每条边有一个流量上限。求从计算机s到t的最大带宽。s发出流... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> 样例输入 ``` 4 5 1 4 1 2 3 1 3 6 2 3 4 2 4 5 3 4 3 ``` 样例输出 ``` 8 ``` ## 建模 本题需要在无向图中求给定源点s到汇点t的最大流。 课本上的最大流是有向图，这里需要把无向边都转化为一对方向相反的有向边边，每对中两条边的容量是相等的，流量是互为相反数的，即如果u到v流量是w，则v到u流量自然是是-w。在增流的时候，按照搜索时形成的方向对对应的“顺向的边”进行读取和操作，“反向边”在修改流量时对称地“反向操作”即可，即顺向边增流delta，那么反向边退流delta。每条边可以增加的流量仍然为(c-w)，其中容量c>0。（如果w<0，那么这条有向边最大可增加c+|w|，相当于反向边的方向退流|w|，再给顺向边增流c（最大可以增到满）。）只要保证按照正确的方向直接读取与操作顺向边，在更新流时对称地操作反向边，每条边的w值就会合法，即落在[-c, c]区间。 ## 算法 应用Edmond-Karp算法。主要操作是从s开始BFS、给到达的点标号、到达t后反过来更新流值。如果某次BFS不能达到t，则说明不存在增流路径，则已得到最大流。 具体来说，借助一个队列从s开始BFS，取出队列的首元素作为“基点”，给探到的点进行标记，内容是它的前驱（本次的“基点”），与到达此点时可增加的最大流。标记完成之后将其加入队列，继续标记其它与“基点”关联的点。标记完成之后，再取出队列的首元素作为“基点”，……（重复以上操作。）直到如果某次取出了t，说明找到一条增流路径，增大的流量为t的标记中的流量delta。于是以t为起始点，根据标记迭代找前驱、更新当前点……每次需要更新从前驱到当前点的顺向边（加上delta），再对称地更新从当前点到前驱的反向边（减去delta）。直到当前点为s，这一次增流完成。于是删除所有标记，重新从s开始BFS。重复操作多次之后，某一次队列中不曾取出t队列就空了，这时就不能再进行增流。这时s的邻边的流量和就是最大流。 ## 实现 ```c++ // Created by Colin on 2020/05/01. // Copyright © 2020 Colin. All rights reserved. // https://blog.valderfield.com/archives/32/ #include <iostream> #include <cstdio> #include <queue> #include <cstring> using namespace std; const int maxn = 102; struct Node { int capacity; int forward; }; class Edmond_Karp { public: Node (*graph)[maxn]; int n, m, s, t; int maxflow; Edmond_Karp(const int _n, const int _m, const int _s, const int _t, Node (*_g)[maxn]): n(_n), m(_m), s(_s), t(_t), graph(_g) { maxflow = 0; } struct Label { int pre; int delta; }; int work() { while (true) { bool reached = 0; Label label[maxn] = { 0 }; bool viewed[maxn] = { 0 }; queue<int> q; q.push(s); viewed[s] = 1; label[s].delta = 0x7ffffff; while (!q.empty()) // BFS { int now = q.front(); q.pop(); if (now != t) { for (int i = 1; i <= n; i++) { if (!viewed[i] && graph[now][i].capacity > 0 && graph[now][i].forward < graph[now][i].capacity) { viewed[i] = 1; q.push(i); // label label[i].pre = now; label[i].delta = min(label[now].delta, graph[now][i].capacity - graph[now][i].forward); } } }//end of if else // now == t { reached = 1; int delta = label[t].delta; while (now != s) // update the flow { int pre = label[now].pre; graph[pre][now].forward += delta; graph[now][pre].forward -= delta; now = pre; } break; } }// end of while if (!reached) break; }// end of while // calculate the max flow for (int i = 1; i <= n; i++) { if (graph[s][i].capacity > 0) maxflow += graph[s][i].forward; } return maxflow; } }; int main() { Node graph[maxn][maxn] = { 0 }; // memset(graph, -0x3f, sizeof(graph)); int n, m, s, t; scanf("%d%d%d%d", &n, &m, &s, &t); for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); graph[u][v].capacity = graph[v][u].capacity = w; } Edmond_Karp ek(n, m, s, t, graph); printf("%d\n", ek.work()); return 0; } ``` Last modification：June 4th, 2021 at 05:18 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 Appreciate the author