EK 46分求助

P3376 【模板】网络最大流

Sktic @ 2021-01-31 18:17:03

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+10;
const ll INF=0xffffffff;
ll n,m,s,t;
struct node
{
    ll v;
    ll val;
    ll nextv;
};
struct node2
{
    int before;
    int b;
};
node c[maxn];
ll vis[maxn]={};
ll hd[maxn];
ll k=1;
node2 p[maxn]={};
void add(ll ur,ll vr,ll valr)
{
    k++;
    c[k].v=vr;
    c[k].val=valr;
    c[k].nextv=hd[ur];
    hd[ur]=k;
}
bool bfs()
{
    memset(p,-1,sizeof(p));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        ll r=q.front();
        for(ll i=hd[r];i!=0;i=c[i].nextv)
        {
            ll h=c[i].v;
            if(vis[h]==0&&c[i].val!=0)
            {
                p[h].before=r;
                p[h].b=i;
                if(h==t)
                    return true;
                vis[h]=1;
                q.push(h);
            } 
        }
        q.pop();
    }
    return false;
}
ll EK()
{
    ll ans=0;
    while(bfs())
    {
        ll mn=INF;
        for(int i=t;i!=s;i=p[i].before)
        {
            mn=min(mn,c[p[i].b].val);
        }
        for(int i=t;i!=s;i=p[i].before)
        {
            c[p[i].b].val=c[p[i].b].val-mn;
            c[p[i].b^1].val=c[p[i].b^1].val+mn;
        }
        ans+=mn;
    }
    return ans;
}
int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,w,0);
    }
    cout<<EK();
    return 0;
}

|