/*
Dinic算法的思路是,用bfs进行分层,限制后面dfs每次的搜索深度,
并且,在dfs的过程中,直接把当前这个路走到u的容量限制分给u的各个出边
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 10020, M = 200020;
typedef long long LL;
struct Edge
{
LL v, c, ne;
} e[M];
int n, m, S, T;
int h[N], idx = 1; // 由于有反向边,所以边要两两配对,这里放弃01这一对,从2,3开始配对
int d[N]; // d数组存储的是每个点在这一轮的层次
int cur[N]; // cur[u]用于存储上次沿着某个路走到u这个点的容量是分配到那个出边被耗完的
void add(int a, int b, int c)
{
e[++idx] = {b, c, h[a]};
h[a] = idx;
}
bool bfs()
{
memset(d, 0, sizeof d); // 每次bfs要重新分层,所以每次一开始要做的是层次初始化为0,同时也可以用d数组判定是否遍历过
//! 这里因为写成sizeof 0错了
queue<int> q;
q.push(S);
d[S] = 1; // 层次从1开始
while (q.size())
{
auto u = q.front();
q.pop();
for (int i = h[u]; i; i = e[i].ne)
{
auto v = e[i].v;
if (d[v] == 0 && e[i].c) // 如果这一次bfs还没有遍历到v,并且uv这条路剩余容量上限不为0
{
d[v] = d[u] + 1;
q.push(v);
if (v == T)
return true; // 只要找到了T就行,找到了T说明T是最深的一层,那么就是说,其他的点都找过了,因此可以直接退出来
}
}
}
return false;
}
LL dfs(int u, LL mf) // 深搜,不断把当前这条都到u的路的容量上限mf分配给u的各个出边
// 并且返回一共分了多少出去
{
if (u == T)
{
return mf; // 如果这个点是汇点,那么就不用往后分了,或者说可以认为是T后面可以分无限多,所以分出去的就是mf
}
LL sum = 0; // 用于记录分了多少出去
for (int i = cur[u]; i; i = e[i].ne) // cur[u]一开始存储的是h[u]也就是u的第一个出边的编号,这里cur用于存储上一次dfs到u是在到个边把容量量上限耗完的,之所以前面的边不用管,是因为一定把那些边都填到上限了才会到这个边
{
cur[u] = i; //! 更新当前弧,这也叫当前弧优化
auto v = e[i].v;
if (d[v] == d[u] + 1 && e[i].c) // 为了限制深搜的深度,要根据bfs分的层来遍历,并且要求这个边剩余的容量上限不为0
{ //! 这里曾经因为等于写成赋值错了
LL f = dfs(v, min(mf, e[i].c)); // 走到v的容量上限是之前走到u的容量上限mf和(u,v)这条边的上限取min,这里是要递归的去求让v把能留到t的容量上限尽可能多的分出去
e[i].c -= f; // (u,v)这条边的容量会减去从v分走的流量
e[i ^ 1].c += f; // 反向边
sum += f; // 从u出去的总流量要加上从v出去的总流量
mf -= f; // 走到u的容量上限被v拿去消耗了
if (mf == 0)
break; // 如果mf已经被消耗完了,说明这次走到u的容量限制已经没有了,直接退出循环,不用再找u的其他子节点了
//! 余量优化
}
}
if (sum == 0)
{
d[u] = 0; // 如果sum=0,说明从u这个点已经无法把流量分出去了,所以u这个点的层次设为0,以后不用再遍历u了
} //! 残枝优化
return sum; // 返回当前这个点可以分出去多少流量
}
LL dinic()
{
LL flow = 0;
while (bfs()) // bfs用于给点分层,返回是否能遍历到T,如果不能就说明图已经没有可以走得增广路了,找不到可行流了
{
memcpy(cur, h, sizeof h); // 将cur初始为每个点的第一个出边
flow += dfs(S, 1e9); // 一开始从S开始,容量上限设为无穷大
}
return flow;
}
int main()
{
cin >> n >> m >> S >> T;
int a, b, c;
while (m--)
{
cin >> a >> b >> c;
add(a, b, c);
add(b, a, 0); // 返现边容量上限初始为0
}
cout << dinic() << endl;
return 0;
}
标签:mf,cur,容量,int,LL,上限,网络,算法,Dinic
From: https://www.cnblogs.com/z4t15/p/17889027.html