网络流
参考资料
简介
网络流（Network Flow）在一张带边容量的有向图上研究流量分配。给定源点 与汇点 ，每条边有容量上限，最大流 问题求从 到 能通过的最大流量。求解核心是不断在 残量网络 中寻找 增广路——一条从 到 、每条边剩余容量均为正的路径，沿路增广并给反向边加回等量流量，直到找不到增广路为止。
Edmonds–Karp 算法
Edmonds–Karp 用 BFS 寻找边数最少的增广路，每次沿路径上的最小残量增广，给正向边减容量、反向边加容量。每轮 BFS 为 ，增广轮数为 ，总时间复杂度为 。
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=505;
struct Edge
{
int v;
ll w;
int id;
};
vector<Edge> G[N];
int pre[N],fa[N];
ll dis[N];
bool vis[N];
int s,t;
void add(int u,int v,ll w)
{
int uid=G[u].size(),vid=G[v].size();
G[u].push_back({v,w,vid});
G[v].push_back({u,0,uid});
}
bool bfs()
{
memset(vis,0,sizeof vis);
queue<int> q;
q.push(s);
vis[s]=1;
dis[s]=inf;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<G[u].size();i++)
{
auto [v,w,id]=G[u][i];
if(!w||vis[v])continue;
dis[v]=min(dis[u],w);
pre[v]=i;
fa[v]=u;
q.push(v);
vis[v]=1;
if(v==t)return 1;
}
}
return 0;
}
ll ans=0;
void update()
{
for(int i=t;i!=s;i=fa[i])
{
G[fa[i]][pre[i]].w-=dis[t];
G[i][G[fa[i]][pre[i]].id].w+=dis[t];
}
ans+=dis[t];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m>>s>>t;
while(m--)
{
int u,v;
ll w;
cin>>u>>v>>w;
add(u,v,w);
}
while(bfs())update();
cout<<ans<<'\n';
return 0;
}
费用流
最小费用最大流（MCMF）在最大流的基础上，要求在流量达到最大的前提下使总费用最小，每条边带有容量与单位流量费用两个属性。
常用 SSP（连续最短路）算法：把最大流中「BFS 找任意增广路」换成「以单位费用为边权找最短的增广路」，每次沿费用最短的增广路增广。找最短路可用 SPFA（允许负费用边）或配合势能的 Dijkstra。
上下界网络流
上下界网络流 给每条边附加流量下界。可行流通过「附加网络」转化为普通最大流：把每条边的流量减去下界，再用虚拟源汇补偿各点流入流出的下界差。在此基础上可进一步求有源汇的最大流、最小流。