《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(50)六魂幡控流量 - 最大网络流(Ford-Fulkerson)
《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(50)六魂幡控流量 - 最大网络流(Ford-Fulkerson)
哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的六魂幡流域,流域中有一张复杂的网络,节点之间的流量各不相同。流域的入口处有一块巨大的石碑,上面刻着一行文字:“欲控此流域,需以六魂幡之力,最大网络流,Ford-Fulkerson显真身。”
哪吒定睛一看,石碑上还有一行小字:“网络的最大流量为...
。”哪吒心中一动,他知道这是一道关于最大网络流的难题,需要通过 Ford-Fulkerson 算法来解决。
暴力解法:六魂幡的初次尝试
哪吒心想:“要找到最大网络流,我可以尝试所有可能的增广路径。”他催动六魂幡之力,从源点开始,逐个路径寻找,试图找到所有可能的增广路径并累加流量。
#include <vector>
#include <climits>
#include <queue>
using namespace std;
struct Edge {
int to, capacity, rev;
Edge(int t, int c, int r) : to(t), capacity(c), rev(r) {
}
};
vector<vector<Edge>> graph;
vector<int> level;
bool bfs(int s, int t) {
fill(level.begin(), level.end(), -1);
queue<int> q;
q.push(s);
level[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (Edge &e : graph[u]) {
if (e.capacity > 0 && level[e.to] < 0) {
level[e.to] = level[u] + 1;
q.push(e.to);
if (e.to == t) return true;
}
}
}
return false;
}
int dfs(int u, int t, int flow) {
if (u == t) return flow;
for (Edge &e : graph[u]) {
if (e.capacity > 0 && level[u] < level[e.to]) {
int d = dfs(e.to, t, min