提交记录

代码如下：

#include<deque>
#include<vector>
#include<iostream>
using namespace std;
#define MN 200
#define MM 5000
#define MC (1L<<62)

struct EDGE{
    long frm;
    long to;
    long cap;
    long flw;
};

EDGE E[MM+50];
vector <long> G[MN+50];
long tot;

long n,m;
long S,T;

long EK()
{
    long ret=0;
//    long cntbfs=0;
    while(1){
        deque<long> Q;
        long cur;
        long pr[MN+50];
        for(long i=0;i<=n;i++)
            pr[i]=-1;
        long vis[MN+50]={0};
        vis[S]=MC;
        Q.push_back(S);
//cout<<"BFS Round"<<++cntbfs<<endl;
        while(Q.size())
        {
            cur=Q[0];
            Q.pop_front();
//cout<<"Ready,number of edge:"<<G[cur][0]<<endl;
            for(long i=0,sz=G[cur].size();i<sz;i++)
            {
                long to=E[G[cur][i]].to;
                if(!vis[to] && E[G[cur][i]].cap>E[G[cur][i]].flw)
                {
                    vis[to]+=min(E[G[cur][i]].cap-E[G[cur][i]].flw,vis[cur]);
                    pr[to]=G[cur][i];
                    Q.push_back(to);
//cout<<"Running, current\/next polong:"<<cur<<'\/'<<to<<" flow="<<min(E[G[cur][i]].cap-E[G[cur][i]].flw,vis[cur])<<endl;
                }
            }
            if(vis[T])
                break;
        }
//cout<<"BFS finished!"<<endl;
        if(!vis[T]) break;

        for(long ce=pr[T];ce!=-1;ce=pr[E[ce].frm])
        {
//cout<<"ce:"<<ce<<"pt"<<E[ce].frm<<'-'<<E[ce].to<<endl;
            E[ce].flw+=vis[T];
            E[ce^1].flw-=vis[T];
        }
        ret+=vis[T];
        
    }
    return ret;
}

int main()
{
    cin>>n>>m>>S>>T;
    for(long i=0;i<m;i++)
    {
        long a,b,c;
        cin>>a>>b>>c;
        E[tot].cap=c;E[tot].frm=a;E[tot].to=b;
        G[a].push_back(tot++);
        
        E[tot].cap=0;E[tot].frm=b;E[tot].to=a;
        G[b].push_back(tot++);
        
    }
    cout<<EK()<<endl;
    return 0;
}