【模板】 Ford-Fulkerson算法

 1 #include<vector>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define INF 0x7fffffff
 5 #define MAX_V 210
 6 
 7 using namespace std;
 8 
 9 //用于表示边的结构体
10 struct edge
11 {
12     int to;    //终点
13     int cap;   //容量
14     int rev;   //反向边
15 };
16 
17 int m,n;
18 bool used[MAX_V];        //DFS中用到的访问标记
19 vector<edge> G[MAX_V];   //用于保存图的邻接表，多组数据时要注意初始化
20 
21 //向图中增加一条从_from到_to容量为_cap的边
22 void add_edge(int _from,int _to,int _cap)
23 {
24     edge temp;
25     temp.to=_to;
26     temp.cap=_cap;
27     temp.rev=G[_to].size();
28     G[_from].push_back(temp);
29     temp.to=_from;
30     temp.cap=0;
31     temp.rev=G[_from].size()-1;
32     G[_to].push_back(temp);
33 }
34 
35 //通过DFS寻找增广路
36 int dfs(int v,int t,int f)
37 {
38     if(v==t)
39         return f;
40 
41     used[v]=true;
42     for(int i=0;i<G[v].size();i++)
43     {
44         edge &e=G[v][i];
45         if(!used[e.to]&&e.cap>0)
46         {
47             int d=dfs(e.to,t,min(f,e.cap));
48             if(d>0)
49             {
50                 e.cap-=d;
51                 G[e.to][e.rev].cap+=d;
52                 return d;
53             }
54         }
55     }
56 
57     return 0;
58 }
59 
60 //求解从s到t的最大流
61 int max_flow(int s,int t)
62 {
63     int flow=0;
64     while(true)
65     {
66         memset(used,false,sizeof(used));
67         int f=dfs(s,t,INF);
68         if(f==0)
69             return flow;
70         flow+=f;
71     }
72 }