最大流的增广路算法

讲解

模板题目链接 洛谷P3376

模板来自算法竞赛入门经典（第2版）--刘汝佳

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn = 100010;struct edge //记录这条边的信息
{int from, to, cap, flow; //起点，终点，容量，流量edge(int a, int b, int c, int d) : from(a), to(b), cap(c), flow(d){}//初始化
};
int n, m;
vector<edge> e; //存储边的信息
vector<int> g[maxn]; //邻接表存图，这里存的是边在e里的编号
int a[maxn]; //记录点目前的流量
int p[maxn]; //记录路径，p[i] 即由s到t路径上点i的前一个点，void init(int n) //初始化清空
{for (int i = 0; i <= n;i++)g[i].clear();e.clear();
}void AddEdge(int from,int to,int cap) 
{e.push_back(edge(from, to, cap, 0)); //正向加边e.push_back(edge(to, from, 0, 0));   //反向加边m = e.size();g[from].push_back(m - 2); //正向存图g[to].push_back(m - 1);   //反向存图
}int MaxFlow(int s,int t)
{int ans = 0; //最终返回的答案while (true){memset(a, 0, sizeof(a));queue<int> q; //BFS循环队列q.push(s);a[s]=INF;    //源点水流量设为无穷while(!q.empty()){int x = q.front(); //取出当前流经的点q.pop();for (int i = 0; i < g[x].size();i++) //遍历当前点可以流到的点{edge now = e[g[x][i]];if(a[now.to] == 0 && now.cap > now.flow)//如果当前点没有被水流到过，并且容量大于流量{p[now.to] = g[x][i]; //记录前驱点a[now.to] = min(a[x], now.cap - now.flow);//当前点的流量为上一个点的流量和还可以流的流量的最小值q.push(now.to);//放入队列}}if(a[t]!=0)//如果水流已经流到终点，结束此次循环break;}if(a[t]==0) //如果没有找到增广路，退出循环break;for (int i = t; i != s;i=e[p[i]].from) //回溯找到水流的路径{e[p[i]].flow += a[t];  //把这条路径上的流量加上e[p[i]^1].flow -= a[t]; // 反向边的流量要减少，减少后反向边的容量就会大于流量，就相当于给了水流一个退回去的机会}ans += a[t];}return ans;
}int main()
{int mm,start, ed;cin >> n >> mm >> start >> ed;init(n);for (int i = 0; i < mm; i++){int from, to, cap;cin >> from >> to >> cap;AddEdge(from, to, cap);}cout << MaxFlow(start, ed) << endl;return 0;
}