蒟蒻写的EK由于偷玩原神导致T了#10和#11

记录

除了#10和#11都没跑到10ms

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,s,t;
ll h[2140],e[51450],ne[51450],w[51450],idx;
int st[2140];
int q[214514],l=1,r=1;
ll p[2140],k[2140],ans;

inline void add(int a,int b,int c)
{
    ne[idx]=h[a];
    e[idx]=b;
    w[idx]=c;
    h[a]=idx++;
}

inline bool bfs()
{
    memset(p,0,sizeof p);
    memset(st,0,sizeof st);
    memset(k,0x7f,sizeof k);
    l=1;r=1;
    q[1]=s;
    st[s]=1;

    while(l<=r)
    {

        int x=q[l];
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(!st[y]&&w[i]>0)
            {
                st[y]=1;
                q[++r]=y;
                k[y]=min(k[x],w[i]);
                p[y]=i;

                if(y==t)
                  return true;
            }
            //cout<<i<<' ';
        }

        l++;
    }
    return false;
}

void EK()
{
    while(bfs())
    {
        ans+=k[t];
        for(int i=t;i!=s;i=e[p[i]+1])
        {
            //cout<<i<<' ';
            w[p[i]]-=k[t];
            w[p[i]+1]+=k[t];
        }
        //cout<<k[t]<<'\n';
        /*for(int i=0;i<=idx-1;i+=2)
        cout<<w[i]<<' '<<w[i+1]<<'\n';*/
    }

}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,0);
    }

    EK();

    cout<<ans;

    return 0;
}