网络流简介
网络
网络是指一个有向图 \(G=(V,E)\)。
每条边 \((u,v)\in E\) 都有一个权值 \(c(u,v)\)，称之为容量（Capacity），当 \((u,v)\notin E\) 时有 \(c(u,v)=0\)。
流
设 \(f(u,v)\) 定义在二元组 \((u\in V,v\in V)\) 上的实数函数且满足
容量限制：对于每条边，流经该边的流量不得超过该边的容量，即，\(f(u,v)\leq c(u,v)\)
斜对称性：每条边的流量与其相反边的流量之和为 0，即 \(f(u,v)=-f(v,u)\)
流守恒性：从源点流出的流量等于汇点流入的流量，即 \(\forall x\in V-\{s,t\},\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)\)
那么 \(f\) 称为网络 \(G\) 的流函数。对于 \((u,v)\in E，f(u,v)\) 称为边的 流量，\(c(u,v)-f(u,v)\) 称为边的 剩余容量。整个网络的流量为 \(\sum_{(s,v)\in E}f(s,v)\)，即 从源点发出的所有流量之和。
一般而言也可以把网络流理解为整个图的流量。而这个流量必满足上述三个性质。
注：流函数的完整定义为
其中有两个特殊的点：源点（Source）\(s\in V\) 和汇点（Sink）\(t\in V,(s\neq t)\)。
网络最大流
概述
令 \(G=(V,E)\) 是一个有源汇点的网络，我们希望在 \(G\) 上指定合适的流 \(f\)，以最大化整个网络的流量（即 \(\sum_{(s,v)\in E}f(s,v)\)），这一问题被称作最大流问题（Maximum flow problem）。
AC·code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define int long long
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c==45),c=getchar();
while(isdigit(c)) x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(long long x){
if(x<0) x=-x,putchar(45);
if(x>=10) wt(x/10);
return putchar(x%10|48),void();
}
} using namespace Q;
cs int N=205,M=5005,inf=0x3f3f3f3f;
namespace edge{
struct qwq{
int v,w,nxt;
}e[M<<1];
int h[N];
il void add(int u,int v,int w,int id){
e[id]={v,w,h[u]},h[u]=id;
e[id|1]={u,0,h[v]},h[v]=id|1;
return;
}
} using namespace edge;
namespace Dinic{
int dep[N],now[N];
queue<int> q;
il bool bfs(int s,int t){
memset(dep,0,sizeof(dep));
dep[s]=1,q.push(s);
ri int u,v;
while(!q.empty()){
u=q.front(),q.pop(),now[u]=h[u];
for(ri int i=h[u];i;i=e[i].nxt){
v=e[i].v;
if(!dep[v]&&e[i].w){
dep[v]=dep[u]+1,q.push(v);
}
}
}
return dep[t]!=0;
}
il int dfs(int u,int res,int t){
if(u==t) return res;
ri int tot=res,v,les;
for(ri int i=now[u];i;i=e[i].nxt){
v=e[i].v,now[u]=i;
if(dep[v]==dep[u]+1&&e[i].w){
les=dfs(v,min(e[i].w,tot),t);
e[i].w-=les,e[i^1].w+=les,tot-=les;
if(!tot) break;
}
}
return res-tot;
}
il long long dinic(int s,int t){
ri long long as=0;//不开long long见祖宗
while(bfs(s,t)){
as+=dfs(s,inf,t);
}
return as;
}
} using namespace Dinic;
signed main(){
int n=rd(),m=rd(),s=rd(),t=rd();
for(ri int i=1,u,v,w;i<=m;++i){
u=rd(),v=rd(),w=rd(),add(u,v,w,i<<1);
}
wt(dinic(s,t));
return 0;
}