网络流
1.最大流/最小割
先 bfs 对图分层，这里只走有流量的边。
然后从源点出发 dfs，每次只往层数为 \(d_u+1\) 的点流，这样每次都是最短的路径。
当前弧优化就是把 head 指针移动到这个位置。
还有如果一个点满流就要删掉。
P3376
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const int N=205,M=5005;
const ll inf=1e18;
int n,m,s,t,head[N],edgenum=1,dep[N],cur[N];
struct edge{int to,nxt,val;
}e[M*2];
void add_edge(int u,int v,int w)
{e[++edgenum].nxt=head[u];e[edgenum].to=v;e[edgenum].val=w;head[u]=edgenum;
}
queue<int> q;
bool bfs()
{for(int i=1;i<=n;i++) cur[i]=head[i],dep[i]=1e9;q.push(s),dep[s]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(e[i].val&&dep[v]>n){dep[v]=dep[u]+1;q.push(v);}}}if(dep[t]<=n) return 1;return 0;
}
ll dfs(int u,ll flow)
{
// printf("%d %lld\n",u,flow);if(u==t||flow==0) return flow;ll res=flow;for(int i=cur[u];i;i=e[i].nxt){cur[u]=i;int v=e[i].to,w=e[i].val;if(w&&dep[v]==dep[u]+1){ll k=dfs(v,min(1ll*w,res));res-=k,e[i].val-=k,e[i^1].val+=k;}}if(res==flow) dep[u]=0;return flow-res;
}
int main()
{scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add_edge(u,v,w),add_edge(v,u,0);}ll ans=0;while(bfs()){ans+=dfs(s,inf);}printf("%lld",ans);return 0;
}
2.费用流
先 spfa 找费用最短路，然后把这条路流满，重复这个过程。
P3381
#include<cstdio>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
const int M=5e4+5,N=5005;
const ll inf=1e17;
int n,m,s,t,head[N],edgenum=1;
struct edge{int nxt,to,flow,val;
}e[M*2];
void add_edge(int u,int v,int f,int w)
{e[++edgenum].nxt=head[u];e[edgenum].to=v;e[edgenum].val=w;e[edgenum].flow=f;head[u]=edgenum;
}
int flow[N],pre[N];
ll dis[N],maxf,minc;
bool inq[N];
queue<int> q;
bool spfa()
{for(int i=1;i<=n;i++) flow[i]=0,dis[i]=inf;q.push(s),inq[s]=1,dis[s]=0,flow[s]=1e9;while(!q.empty()){int u=q.front();inq[u]=0;q.pop();for(int i=head[u];i;i=e[i].nxt){int v=e[i].to,f=e[i].flow,w=e[i].val;if(f&&dis[v]>dis[u]+w){dis[v]=dis[u]+w,flow[v]=min(flow[u],f);pre[v]=i;if(!inq[v]) inq[v]=1,q.push(v);}}}if(dis[t]<inf) return 1;return 0;
}
void MCMF()
{maxf+=flow[t],minc+=flow[t]*dis[t];int x=t;while(x!=s){e[pre[x]^1].flow+=flow[t],e[pre[x]].flow-=flow[t];x=e[pre[x]^1].to;}
}
int main()
{scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++){int u,v,w,c;scanf("%d%d%d%d",&u,&v,&w,&c);add_edge(u,v,w,c),add_edge(v,u,0,-c);}while(spfa()){
// printf("a");MCMF();}printf("%lld %lld",maxf,minc);return 0;
}