一、从概念入手
网络流用于解决流量问题，同样，我们可以用网络流来解决其简化版本：二分图。
网络流:所有弧上流量的集合f={f(u,v)},称为该容量网络的一个网络流.
定义：带权的有向图G=(V,E)，满足以下条件，则称为网络流图(flow network)：
仅有一个入度为0的顶点s，称s为源点仅有一个出度为0的顶点t，称t为汇点每条边的权值都为非负数，称为该边的容量，记作c(i,j)。弧的流量:通过容量网络G中每条弧< u,v>,上的实际流量(简称流量),记为f(u,v);
对于任意一个时刻，设f(u,v)实际流量，则整个图G的流网络满足3个性质：
容量限制：对任意u,v∈V，f(u,v)≤c(u,v)。斜对称性：对任意u,v∈V，f(u,v) = -f(v,u)。从u到v的流量一定是从v到u的流量的相反值。流量守恒定律：对任意u，若u不为S或T，一定有∑f(u,v)=0，(u,v)∈E。即u到相邻节点的流量之和为0，因为流入u的流量和u点流出的流量相等，u点本身不会"制造"和"消耗"流量。可行流:在容量网络G中满足以下条件的网络流f,称为可行流.
a.弧流量限制条件: 0<=f(u,v)<=c(u,v); b:平衡条件:即流入一个点的流量要等于流出这个点的流量,(源点和汇点除外).零流 若网络流上每条弧上的流量都为0,则该网络流称为零流. 伪流:如果一个网络流只满足弧流量限制条件,不满足平衡条件,则这种网络流为伪流,或称为容量可行流.(预流推进算法有用)
在容量网络中,满足弧流量限制条件,且满足平衡条件并且具有最大流量的可行流,称为网络最大流,简称最大流.
=============================================================================
以上是网络流的定义内容，我们就聊到这里。
那么怎么求最大流呢？
我们的方法有两种：增广路算法系列和预流推进算法系列
我们先来比较一下时间复杂度：
Edmonds-KarpO(VE^2) DinicO(V^2E)ISAP(Improved Shortest Augmenting Path)
O(V^2E)（常数小）预流推进(Preflow-push method)（算导内称为推送-重贴标签）O(V^2E)最高标号预流推进（Highest-label preflow-push algorithm)O(V^2*sprt(E))E前置预流推进O(V^3)注意我们的ISAP的常数是非常优秀的，几乎不能被卡掉，甚至比时间复杂度少的HLPP还优秀，在随机数据下，洛谷p3376跑分比Dinic算法少一个500~600ms
我们回到事发现场，文明从这里起步！那么我们可以看到，ISAP是非常优秀的，那么怎么VAN呢？
求解最大流问题的一个比较容易想到的方法就是，每次在残量网络（residual network）中任意寻找一条从 s 到 t 的路径，然后增广，直到不存在这样的路径为止。这就是一般增广路算法（labeling algorithm）。可以证明这种不加改进的贪婪算法是正确的。假设最大流是f，那么它的运行时间为O(fE)。但是，这个运行时间并不好，因为它和最大流f有关。
人们发现，如果每次都沿着残量网络中的最短增广路增广，则运行时间可以减为 O(E^2V)。这就是最短增广路算法。
ISAP（Improved Shortest Augmenting Path）(%ISA)也是基于分层思想的最大流算法。所不同的是，它省去了Dinic每次增广后需要重新构建分层图的麻烦，而是在每次增广完成后自动更新每个点的『标号』（也就是所在的层）
最短增广路算法是一种运用距离标号使寻找增广路的时间复杂度下降的算法。所谓的距离标号就是某个点到汇点的最少的弧的数量(即当边权为1时某个点的最短路径长度). 设点i的标号为d[i], 那么如果将满足d[i] = d[j] + 1, 且增广时只走允许弧, 那么就可以达到”怎么走都是最短路”的效果. 每个点的初始标号可以在一开始用一次从汇点沿所有反向的BFS求出.
概括地说，ISAP 算法就是不停地找最短增广路，找到之后增广；如果遇到死路就 retreat，直到发现s, t不连通，算法结束。找最短路本质上就是无权最短路径问题，因此采用 BFS 的思想。具体来说，使用一个数组d，记录每个节点到汇点t的最短距离。搜索的时候，只沿着满足d[u]=d[v]+1的边u→v（这样的边称为允许弧）走。显然，这样走出来的一定是最短路。
如果学过Dinic算法的童鞋这里就可以发现，ISAP本质上就是去掉BFS的Dinic，然后加上一些适应的工件，因此它的时间复杂度不变，仍然是O(V^2E)，但是烧掉了反复BFS的部分，因此常数优秀！
[例题]
给出一个网络图，以及其源点和汇点，求出其网络最大流。
[分析]
真~裸题！
我们直接看代码：
这个代码的注释版如下：
int source; // 源点 int sink; // 汇点 int lst[max_nodes]; // 可增广路上的上一条弧的编号 int num[max_nodes]; // 和 t 的最短距离等于 i 的节点数量 int cur[max_nodes]; // 当前弧下标 int dis[max_nodes]; // 残量网络中节点 i 到汇点 t 的最短距离 bool vis[max_nodes];BFS代码
注意，这个扫描是逆向的qwq
现在是扫描出增广路径
下面的部分就是ISAP的核心了...
#include<cstdio> #include<cctype> #include<algorithm> using std::max; using std::min; #include<queue> using std::queue; #ifdef __GNUG__ #pragma g++ optimize("O3"); #endif #ifdef __GNUC__ #pragma gcc optimize("O3"); #endif #ifdef __linux #define getchar getchar_unlocked #define putchar putchar_unlocked #endif template<typename int_type> inline int_type next_int(int_type &ret) { int neg=false; int bit=getchar(); while(!isdigit(bit)) { if(bit=='-') neg^=true; bit=getchar(); } ret=0; while(isdigit(bit)) { ret=(ret<<3)+(ret<<1)+(bit^'0'); bit=getchar(); } return ret=neg?~ret+1:ret; } template<typename int_type> inline void writeln(int_type op) { int size=0; char ret[30]={}; if (!op) putchar('0'); else if(op<0) { putchar('-'); op=~op+1; } while(op) { ret[++size]=(op)+'0'; op/=10; } while(size) putchar(ret[size--]); putchar('\n'); return; } const int max_node=1e4+4; const int max_edge=2e5+5; const int inf=0x3f3fcfcf; int nodes=0,edges=0; int s=0,t=0; struct edge_node { int u,v; int next; int flow; int cap; } edge[max_edge]={}; struct node_node { int rec; int dis,cur; int lst; bool vis; } node[max_node]={}; int num[max_node]={}; int cnt=0; inline void plus_edge(int x,int y,int z) { edge[++cnt].u=x; edge[cnt].v=y; edge[cnt].cap=z; edge[cnt].next=node[x].rec; node[x].rec=cnt; edge[++cnt].u=y; edge[cnt].v=x; edge[cnt].next=node[y].rec; node[y].rec=cnt; return; } void bfs_dis(void) { queue<int>que; node[t].vis=true; que.push(t); while(!que.empty()) { int k=que.front(); que.pop(); for(int i=node[k].rec;i;i=edge[i].next) { if(node[edge[i].u].vis==false&&edge[i].cap==0) { node[edge[i].u].vis=true; node[edge[i].u].dis=node[k].dis+1; que.push(edge[i].u); } } } return; } int find_augment(void) { int ptr=t; int res=inf; while(ptr^s) { res=min(res,edge[node[ptr].lst].cap-edge[node[ptr].lst].flow); ptr=edge[node[ptr].lst].u; } ptr=t; while(ptr^s) { edge[node[ptr].lst].flow+=res; edge[node[ptr].lst^1].flow-=res; ptr=edge[node[ptr].lst].u; } return res; } int isap_net(void) { bfs_dis(); int res_flow=0; int ptr=s; for(int i=1;i<=nodes;i++) { num[node[i].dis]++; node[i].cur=node[i].rec; } while(node[s].dis<nodes) { if(ptr==t) { res_flow+=find_augment(); ptr=s; } bool flag=false; for(int i=node[ptr].cur;i;i=edge[i].next) { if(edge[i].cap>edge[i].flow&&node[ptr].dis==node[edge[i].v].dis+1) { flag=true; node[edge[i].v].lst=i; node[ptr].cur=i; ptr=edge[i].v; break; } } if(flag==false) { if(--num[node[ptr].dis]==0) break; int temp=nodes-1; for(int i=node[ptr].rec;i;i=edge[i].next) { if(edge[i].cap>edge[i].flow) temp=min(temp,node[edge[i].v].dis); } node[ptr].dis=temp+1; num[node[ptr].dis]++; node[ptr].cur=node[ptr].rec; if(ptr^s) ptr=edge[node[ptr].lst].u; } } return res_flow; } void work(void) { nodes=next_int(nodes); edges=next_int(edges); s=next_int(s); t=next_int(t); cnt++; int x=0,y=0,z=0; for(int i=1;i<=edges;i++) { x=next_int(x); y=next_int(y); z=next_int(z); plus_edge(x,y,z); } writeln(isap_net()); return; } int main(int arc,char *argv[],char *env[]) { work(); return 0; }