ネットワークストリーム最大ストリームEdmonds-Karp拡張アルゴリズム

EKアルゴリズムの構想は非常に簡単で,拡張経路(BFS)をずっと探し,もしあれば,拡張路の最小値k,ans+=kを記録し,ネットワークの値(逆エッジを用いる)を更新することである.
テンプレート:

#include
#include
#include
#include
#include
#include
#define N 10005
#define M 200005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,s,t,cnt=1,head[N],incf[N],pre[N],maxflow; 
bool vis[N];

struct Node{
    int to,nxt,val;
}edge[M];

void add(int x,int y,int z)
{
    cnt++;
    edge[cnt].to=y;
    edge[cnt].nxt=head[x];
    edge[cnt].val=z;
    head[x]=cnt;
}

bool bfs()//      
{
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(s);  vis[s]=1;  incf[s]=inf;
    while(q.size())
    {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=edge[i].nxt)
        {
            if(edge[i].val)
            {
                int v=edge[i].to;
                if(vis[v]) continue;
                incf[v]=min(incf[u],edge[i].val);
                pre[v]=i;            //    ，            
                q.push(v);  vis[v]=1;
                if(v==t) return true; 
            }
        }
    }
    return false;
}

void update()//   - ，   +  
{
    int x=t;
    while(x!=s)
    {
        int i=pre[x];
        edge[i].val-=incf[t];
        edge[i^1].val+=incf[t];
        x=edge[i^1].to;
    }
    maxflow+=incf[t];
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z); add(y,x,0);//     
    }
    while(bfs()) update();
    printf("%d",maxflow);
    return 0;
}