FF算法,60分 4、7、8、9点为什么过不了

P3376 【模板】网络最大流

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

戳我解惑


|