loj117_有源汇有上下界最小流

#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;

const int N=125100;
int n,m,s,t,tot=1,hd[(int)6e4],cur[(int)6e4],ss,tt,dep[(int)6e4];
long long flow[(int)6e4],l[N];
struct Edge
{
    int to,nxt;
    long long val;
}e[N*3+99];
inline void add(int u,int v,long long w){
    e[++tot]={v,hd[u],w},hd[u]=tot;
    e[++tot]={u,hd[v],0ll},hd[v]=tot;
}

bool bfs(int st,int en){
    for(int i=0;i<=n+2;++i)dep[i]=0;
    queue<int> q;
    memcpy(cur,hd,sizeof(hd));
    q.push(st);
    dep[st]=1;

    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int eg=hd[u];eg;eg=e[eg].nxt){
            if(!dep[e[eg].to]&&e[eg].val>0){
                dep[e[eg].to]=dep[u]+1;
                q.push(e[eg].to);
            }
        }
    }
    return !!dep[en];
}

long long dfs(int u,int en,long long flow){
    //printf("%d-%d\n",u,en);
    if(u==en)return flow;
    long long r=flow;
    for (int eg = cur[u]; eg && r; eg = e[eg].nxt)
    {
        //printf("%d-(%d---%d)-%d__%lld\n",eg,e[eg].to,u,e[eg].nxt,r);
        cur[u] = eg;
        if (e[eg].val>0 && dep[e[eg].to] == dep[u] + 1)
        {
            long long c = dfs(e[eg].to,en, min(r, e[eg].val));
            //printf("%lld\n",c);
            r -= c;
            e[eg].val -= c;
            e[eg ^ 1].val += c;
        }
    }
    return flow - r;
}

long long Dinic(int st,int en){
    long long ret=0;
    while(bfs(st,en))ret+=dfs(st,en,1ll<<53);
    //printf("%lld__\n",ret);
    return ret;
}

int main(){
    long long tmp,sum=0;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    tt=n+1;
    for(int i=1,w,x;i<=m;++i){
        long long y,z;
        scanf("%d%d%lld%lld",&w,&x,&y,&z);
        l[i]=y;
        add(w,x,z-y);
        flow[w]-=l[i],flow[x]+=l[i];
    }
    for(int i=1;i<=n;++i){
        if(flow[i]>0){
            sum+=flow[i];
            add(ss,i,flow[i]);
        }else if(flow[i]<0)add(i,tt,-flow[i]);
    }
    add(t,s,1ll<<53);
    if(sum==Dinic(ss,tt)){
        tmp=e[tot].val;
        e[tot].val=e[tot^1].val=0;
        printf("%lld\n",tmp - Dinic(t, s));
    }else puts("please go home to sleep");
    return 0;
}