https://oi-wiki.org/graph/flow/max-flow/
by StudyingFather @ 2019-12-13 20:01:04
建议直接看 OI-wiki
by StudyingFather @ 2019-12-13 20:01:14
@[StudyingFather](/user/22030) 没有SAP 。。
by 我去 @ 2019-12-13 20:04:06
SAP 算法就是 EK（或者说，是一类算法的统称？
by 木木！ @ 2019-12-13 20:09:35
网上说法很多……有些说 SAP 就是 EK，有些把 SAP 和 ISAP 弄混了……我倾向于相信 SAP 是代指所有寻找最短增广路的算法，例如 EK、Dinic 之类。
by 木木！ @ 2019-12-13 20:11:00
@[我去](/user/48316)
by 木木！ @ 2019-12-13 20:12:24
@[我去](/user/48316) 喜欢用Dinic
by RinkaSnow @ 2019-12-13 20:32:58
@[木木！](/user/49458) 那julao您看看这是啥算法啊
```cpp
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
using namespace std;
const int MAXN = 10010;
const int MAXM = 100010;
const int INF = 0x3f3f3f3f;
template <typename T>
inline void read(T&x){
x=0; char temp=getchar(); bool f=false;
while(!isdigit(temp)){if(temp=='-') f=true; temp=getchar();}
while(isdigit(temp)){x=(x<<1)+(x<<3)+temp-'0'; temp=getchar();}
if(f) x=-x;
}
template <typename T>
void print(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
//basic
int n,m,s,t;
//save edge
struct node{
int to,next,val;
}edge[MAXM<<1];
int head[MAXN],cnt=1;
//SAP
int dist[MAXN],gap[MAXN];
inline void AddEdge(int u,int v,int w){
edge[++cnt]=(node){v,head[u],w};
head[u]=cnt;
}
int Dfs(int id,int flow){
if(id==t||flow==0) return flow;
int maxflow=0;
for(register int i=head[id];i;i=edge[i].next){
int aim=edge[i].to;
if(edge[i].val&&dist[aim]+1==dist[id]){
int temp=Dfs(aim,min(flow,edge[i].val));
edge[i].val-=temp,edge[i^1].val+=temp;
maxflow+=temp,flow-=temp;
if(dist[s]==n||flow==0) return maxflow;
}
}
if(--gap[dist[id]]==0) dist[s]=n;
gap[++dist[id]]++;
return maxflow;
}
inline void SAP(){
int ans=0;
gap[0]=n;
while(dist[s]<n) ans+=Dfs(s,INF);
print(ans);
}
int main(){
read(n),read(m),read(s),read(t);
for(register int i=1;i<=m;i++){
int u,v,w; read(u),read(v),read(w);
AddEdge(u,v,w); AddEdge(v,u,0);
}
SAP();
return 0;
}
```
by 我去 @ 2019-12-13 20:36:40
@[tzxydby](/user/237660) 您开心就好
by 我去 @ 2019-12-13 20:37:26
@[我去](/user/48316) 是ISAP
by WAutomaton @ 2019-12-13 20:59:52