quefeng123 @ 2024-06-27 13:14:24
#include <algorithm>
#include <chrono>
#include <climits>
#include <fstream>
#include <iostream>
#include <istream>
#include <queue>
#include <ratio>
#include <set>
#include <string>
#include <vector>
using namespace std;
const long long INF =2147483649; // 定义一个很大的值作为无穷大
class FlowGraph {
public:
int num; // 总节点个数
int s; // 源节点坐标
int t; // 汇节点坐标
int teamStart; // 队伍开始编号
int remainGamesNum; // 剩余比赛容量
vector<vector<long long>> capacity; // 边容量
vector<vector<long long>> flow; // 流量
vector<vector<int>> adj; // 邻接表
FlowGraph(int num)
: num(num), adj(num), remainGamesNum(0),
capacity(num, vector<long long>(num, 0)),
flow(num, vector<long long>(num, 0)) {}
void add(int from, int to, long long cap) {
// 正向边
adj[from].push_back(to);
capacity[from][to] = cap;
flow[from][to] = 0;
// 反向边
adj[to].push_back(from);
capacity[to][from] = 0;
flow[to][from] = 0;
}
static FlowGraph create(istream &in) {
int n, t, from, to;
long long cap;
in >> n;
FlowGraph g(n);
in >> t;
in >> g.s >> g.t;
g.s--;
g.t--;
while (t--) {
in >> from >> to >> cap;
g.add(from - 1, to - 1, cap);
}
return g;
}
};
class Solution {
public:
string name;
Solution(string name) : name(name) {}
virtual long long getMaxFlow(FlowGraph &graph) = 0;
};
struct Node {
int no;
long long cf;
friend bool operator<(Node n1, Node n2) { return n1.cf < n2.cf; }
};
static FlowGraph noneG(0);
class FordFulkerson : public Solution {
protected:
vector<vector<long long>> &capacity; // 容量
vector<vector<long long>> &flow; // 流量
vector<vector<int>> &adj; // 邻接表
int s, t; // 源节点、汇节点
vector<bool> visited; // 记录节点是否被访问过
// 使用深度优先搜索寻找增广路径,并返回路径上的最小剩余容量
long long findPathCf(int current, long long minCf) {
if (current == t) {
return minCf;
}
visited[current] = true;
long long cap, f;
int to;
for (auto &to : adj[current]) {
cap = capacity[current][to], f = flow[current][to];
if (!visited[to] && cap > f) {
long long cf = findPathCf(to, min(minCf, cap - f));
// 回溯时,发现找到t的路径,开始更新当前的路径上的流量值
if (cf > 0) {
// 正向边流量增加,反向边流量减少
flow[current][to] += cf;
flow[to][current] -= cf;
return cf;
}
}
}
return 0; // 未找到增广路径,返回0表示结束算法
}
public:
FordFulkerson()
: capacity(noneG.capacity), flow(noneG.flow), adj(noneG.adj),
Solution("FordFulkerson") {}
long long getMaxFlow(FlowGraph &g) {
// 初始变量
s = g.s, t = g.t;
capacity = g.capacity, flow = g.flow, adj = g.adj;
visited.resize(g.num, false);
long long maxFlow = 0;
long long cf = 0;
// 使用dfs查找相关增广路径,边查边更新
while ((cf = findPathCf(s, INF)) > 0) {
// 清除标记点
fill(visited.begin(), visited.end(), false);
maxFlow += cf;
}
return maxFlow;
}
};
// 洛谷测试
int main() {
FlowGraph g = FlowGraph::create(cin);
Solution *s = new FordFulkerson;
cout << s->getMaxFlow(g);
return 0;
}
by toolazy @ 2024-06-27 13:37:21
戳我解惑