【模闆】EK求最大流

求解最大流問題的最簡便方法

但是效率不是很理想

參考部落格：網絡流-最大流

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=,maxe=;
int n,e,que[maxn],fa[maxn],id[maxn],ans;
bool vis[maxn];
struct data{
    int son[maxe],nxt[maxe],lnk[maxn],tot;
    int flw[maxe],cap[maxe];
    void add(int x,int y,int w){
        son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
        flw[tot]=;cap[tot]=w;
    }
}a;
inline int red(){
    int tot=;char ch=getchar();
    while (ch<'0'||'9'<ch) ch=getchar();
    while ('0'<=ch&&ch<='9') tot=tot*+ch-,ch=getchar();
    return tot;
}
bool bfs(){
    memset(vis,,sizeof(vis));
    int hed=,til=;
    que[]=;vis[]=;
    while (hed!=til)
     for (int j=a.lnk[que[++hed]];j;j=a.nxt[j])
      if (!vis[a.son[j]]&&a.cap[j]>a.flw[j]){
        que[++til]=a.son[j];vis[a.son[j]]=;
        fa[a.son[j]]=que[hed];id[a.son[j]]=j;
        if (a.son[j]==n) return ;
      }
    return ;
}
int main(){
    n=red(),e=red();a.tot=;
    for (int i=,x,y,w;i<=e;i++)
     x=red(),y=red(),w=red(),a.add(x,y,w),a.add(y,x,);
    while (bfs()){
        int Min=;
        for (int x=n;x!=;x=fa[x])
         Min=min(Min,a.cap[id[x]]-a.flw[id[x]]);
        ans+=Min;
        for (int x=n;x!=;x=fa[x])
         a.flw[id[x]]+=Min,a.flw[id[x]^]-=Min;
    }
    printf("%d",ans);
    return ;
}