最大流
网络流图里，源点流出的量，等于汇点流入的量，除源汇外的任何点，其流入量之和等于流出量之和
残余网络
在一个网络流图上，找到一条源到汇的路径（即找到了一个流量）后，对路径上所有的边，其容量都减去此次找到的流量，对路径上所有的边，都添加一条反向边，其容量也等于此次找到的流量，这样得到的新图，就称为原图的“残余网络”
Ford-Fulkerson
求最大流的过程，就是不断找到一条源到汇的路径，然后构建残余网络，再在残余网络上寻找新的路径，使总流量增加，然后形成新的残余网络，再寻找新路径…..直到某个残余网络上找不到从源到汇的路径为止，最大流就算出来了。
每次寻找新流量并构造新残余网络的过程，就叫做寻找流量的“增广路径”，也叫“增广”
时间复杂度为C*(m+n)
Edmonds-Karp
在每次增广的时候，选择从源到汇的具有最少边数的增广路径,即不是通过dfs寻找增广路径，而是通过bfs寻找增广路径。
这就是Edmonds-Karp 最短增广路算法,一般叫EK算法
复杂度上限为n*m^2(n是点数，m是边数)
int n,s,e; //n个点,起点,终点
int a[maxn][maxn]; //图,邻接矩阵
int pre[maxn]; //记录路径
bool vis[maxn];
int bfs() //源点start,汇点end
{
mem(vis,0);mem(pre,0);
vis[s] = 1,pre[s] = 0;
queue<int> q;
q.push(s);
bool find = false; //是否找到
while(!q.empty())
{
int v = q.front();q.pop();
for(int i = 1; i <= n; i++)
{
if(a[v][i] > 0 && !vis[i])
{
pre[i] = v;vis[i] = 1;
if(i == e) //找到汇点
{
find = true;
break;
}
}
}
}
if(find)
{
int res = inf,v = e; //求出最小的流
while(pre[v])
{
res = min(res,a[pre[v]][v]);
v = pre[v];
}
v = e; //构建残余网络
while(pre[v])
{
a[pre[v]][v] -= res; //每条边减去最小流
a[v][pre[v]] += res; //建反向边
v = pre[v];
}
return res;
}
return 0;
}
Dinic
Edmonds-Karp的提高余地：需要多次从s到t调用BFS，可以设法减少调用次数。
时间复杂度(n * n * m)
- 先利用 BFS对残余网络分层
- 利用 BFS对残余网络分层，分完层后，利用DFS从前一层向后一层反复寻找增广路。
- DFS过程中，要是碰到了汇点，则说明找到了一条增广路径。此时要增加总流量的值，消减路径上各边的容量，并添加反向边，即所谓的进行增广
- DFS找到一条增广路径后，并不立即结束，而是回溯后继续DFS寻找下一个增广路径。
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define cin(a) scanf("%d",&a)
#define pii pair<int,int>
#define ll long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 10100; //点数
const int maxm = 200100; //边数的两倍
int n,m,s,e,cnt;
int cost[maxm],to[maxm],Next[maxm]; //链式前向星
int head[maxn];
int level[maxn];
void add(int u,int v,int w) //建图
{
to[cnt] = v,cost[cnt] = w;
Next[cnt] = head[u],head[u] = cnt;
cnt++;
}
bool bfs()
{
mem(level,-1);
level[s] = 0;
queue<int> q; q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = Next[i])
{
int v = to[i];
if(cost[i] > 0 && level[v] == -1)
{
level[v] = level[u] + 1;
if(v == e) return true;
q.push(v);
}
}
}
return false;
}
int dfs(int u,int flow)
{
if(u == e) return flow;
int res = flow;
for(int i = head[u]; i != -1; i = Next[i])
{
if(res==0) break;
int v = to[i];
if(cost[i] > 0 && level[v] == level[u] + 1)
{
int k = dfs(v,min(res,cost[i])); //深搜
res -= k; cost[i] -= k; cost[i^1] += k; //用res的值来控制回溯,回溯到最小流量的前一条边,继续深搜
}
}
return flow-res; //返回用掉的流量
}
int dinic()
{
int ans = 0;
while(bfs())
{
ans += dfs(s,inf);
}
return ans;
}
int main()
{
mem(head,-1);cnt = 0;
scanf("%d%d%d%d",&n,&m,&s,&e);
for(int i = 0,u,v,w; i < m; i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,0);
}
printf("%d\n",dinic());
return 0;
}
dinic弧优化
和原来的代码区别不打，用一个数组记录\(head\)数组，然后跑过的边就丢掉去就行了，稍稍改动一下代码就能跑的飞快
int head[maxn],cost[maxm],to[maxm],Next[maxm],cnt = 2;
void add(int u,int v,int w)
{
to[cnt] = v;cost[cnt] = w;Next[cnt] = head[u];head[u] = cnt;cnt++;
}
//用cur代替head是为了修改cur而不改变head，以保证改变可行弧而不改变边与起点的对应关系
int cur[maxn]; //head
int level[maxn];
int q[maxn];
bool bfs()
{
mem(level,0);
level[s] = 1;
int h = 1,r = 1;
q[1] = s;
while(h <= r)
{
int u = q[h++];
for(int i = head[u]; i ; i = Next[i])
{
int v = to[i];
if(cost[i] && !level[v])
{
level[v] = level[u]+1;
if(v == t) return true;
q[++r] = v;
}
}
}
return false;
}
int dfs(int u,int flow)
{
if(u == t) return flow;
int res = flow;
for(int i = cur[u]; i ; i = Next[i])
{
if(res == 0) break;
cur[u] = i; //弧优化,每次跑完了就丢掉这个边
int v = to[i];
if(cost[i] && level[v] == level[u]+1)
{
int k = dfs(v,min(res,cost[i]));
res -= k;cost[i] -= k;cost[i^1] += k;
}
}
return flow - res;
}
int dinic()
{
int flow = 0;
while(bfs())
{
memcpy(cur,head,sizeof(head)); //复制head数组
flow += dfs(s,inf);
}
return flow;
}