查找图上两个节点之间的最大流量

2 回答

• 0

  找到具有最大流量的路径等同于找到具有最低容量的边缘最大化的路径 . 因此，您可以使用一些路径寻找算法并对其进行扩展，以跟踪路径上看到的最低边缘容量 . 对于DFS，您甚至可以保持下限，这是您目前看到的最大容量路径 . 然后，您无需在搜索时考虑任何容量较小的边缘，因为具有此类边缘的任何路径都不能具有比您已找到的路径更高的容量 .

  回复于 2024-05-04T09:45:10+08:00
• 0

  不确定您对独特路径的规则是什么;

  typedef std::list<int> Path;
  typedef std::list<Path> Paths;
  
  class Node {
  public:
      Node() : visited(false) { }
      bool visited;
      Path edge;
  };
  
  const int max_nodes = 1000;
  Node nodes[max_nodes];
  
  bool visitNode(Path &out,int node,int target) {
      if (node == target)
          return true;
      Node& n = nodes[node];
      if (n.visited) 
          return false;
      n.visited = true;
      for (Path::iterator it = n.edge.begin(); it != n.edge.end(); it++) {
          if (visitNode(out,*it,target)) {
              out.push_back(node);
              return true;
          }
      }
      return false;
  }
  
  void resetNodes() {
      for (int i = 0; i < max_nodes; i++) 
          nodes[i].visited = false;
  }
  
  Paths findPaths(int node,int target) {
      resetNodes()
      ...
  }
  

  回复于 2024-05-04T09:45:10+08:00