最大流Ford_Fulkerson

本文主要是介绍最大流Ford_Fulkerson，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

#include<iostream>
#include<vector>
using namespace std;
#define INF 0x0fffffff
#define min(a,b)(a<b?a:b)
#define MAX_V 1000
struct edge
{
 int to,cap,rev; //指向to的反向边的标号
 edge(){}
 edge(int a,int b,int c):to(a),cap(b),rev(c){}
};
vector<edge>G[MAX_V];
bool used[MAX_V];

void add_edge(int from,int to,int cap) 
{
 G[from].push_back(edge(to,cap,G[to].size()));  
 G[to].push_back(edge(from,0,G[from].size()-1));
}

int dfs(int v,int t,int f)
{
 if(v==t)
  return f;
 used[v]=true;
 for(int i=0;i<G[v].size();i++)
 {
  edge &e=G[v][i];
  if(!used[e.to]&&e.cap>0)
  {
   int d=dfs(e.to,t,min(f,e.cap));
   if(d>0)
   {
    e.cap-=d;
    G[e.to][e.rev].cap+=d;
    return d;
   }
  }
 }
 return 0;
}
int max_flow(int s,int t)
{
 int flow=0;
 while(1)
 {
  memset(used,0,sizeof(used));
  int f=dfs(s,t,INF); //每次找到一条可行流
  if(f==0) return flow;
  flow+=f;
 }
 return flow;
}
int main()
{
 
}

 

这篇关于最大流Ford_Fulkerson的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---