有源汇上下界最大流

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int maxm = 4e5+5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct Edge{
    int to;
    int next;
    ll cap;
    ll flow;
};
Edge edge[maxm];
int head[maxn];
int tol;

namespace ULNflows_max{
    int gap[maxn], dep[maxn], cur[maxn];
    int Q[maxn], s[maxn];
    ll more[maxn];
    void addedge(int u, int v, ll w, ll rw = 0){
        edge[tol].to = v;
        edge[tol].cap = w;
        edge[tol].flow = 0;
        edge[tol].next = head[u];
        head[u] = tol++;
        edge[tol].to = u;
        edge[tol].cap = rw;
        edge[tol].flow = 0;
        edge[tol].next = head[v];
        head[v] = tol++;
    }
    void bfs(int start, int end){
        memset(dep, -1, sizeof(dep));
        memset(gap, 0, sizeof(gap));
        gap[0] = 1;
        int front = 0, rear = 0;
        dep[end] = 0;
        Q[rear++] = end;
        while(front != rear){
            int u = Q[front++];
            for(int i = head[u]; i != -1; i = edge[i].next){
                int v = edge[i].to;
                if(dep[v] != -1)    continue;
                Q[rear++] = v;
                dep[v] = dep[u] + 1;
                gap[dep[v]]++;
            }
        } 
    }
    ll isap(int start, int end, int n){//起点,终点,点的个数
        bfs(start, end);
        memcpy(cur, head, sizeof(head));
        int top = 0;
        int u = start;
        ll ans = 0;
        while(dep[start] < n){
            if(u == end){
                ll Min = INF;
                int inser;
                for(int i = 0; i < top; i++){
                    if(Min > edge[s[i]].cap - edge[s[i]].flow){
                        Min = edge[s[i]].cap - edge[s[i]].flow;
                        inser = i;
                    }
                }
                for(int i = 0; i < top; i++){
                    edge[s[i]].flow += Min;
                    edge[s[i]^1].flow -= Min;
                }
                ans += Min;
                top = inser;
                u = edge[s[top]^1].to;
                continue;
            }
            bool flag = false;
            int v;
            for(int i = cur[u]; i != -1; i = edge[i].next){
                v = edge[i].to;
                if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
                    flag = true;
                    cur[u] = i;
                    break;
                }
            }
            if(flag){
                s[top++] = cur[u];
                u = v;
                continue;
            }
            int Min = n;
            for(int i = head[u]; i != -1; i = edge[i].next){
                if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min){
                    Min = dep[edge[i].to];
                    cur[u] = i;
                }
            }
            gap[dep[u]]--;
            if(!gap[dep[u]])    return ans;
            dep[u] = Min + 1;
            gap[dep[u]]++;
            if(u != start)    u = edge[s[--top]^1].to;
        }
        return ans;
    }
}
void init(){
    tol = 0;
    memset(head, -1, sizeof(head));
    memset(ULNflows::more, 0, sizeof(ULNflows::more));
}
int n, m;
int main(){
    init();
    int s, t;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    int ss = n+1, tt = n+2;
    for(int i = 1; i <= m; i++){
        int u, v;
        ll up, low;
        scanf("%d%d%lld%lld", &u, &v, &low, &up);
        ULNflows::addedge(u, v, up-low);
        ULNflows::more[u] -= low;
        ULNflows::more[v] += low;
    }
    ll maxflow = 0;
    for(int i = 1; i <= n; i++){
        if(ULNflows::more[i] > 0)    ULNflows::addedge(ss, i, ULNflows::more[i]), maxflow += ULNflows::more[i];
        else if(ULNflows::more[i] < 0)    ULNflows::addedge(i, tt, -ULNflows::more[i]);
    }
    ULNflows::addedge(t, s, INF);
    if(maxflow == ULNflows::isap(ss, tt, n+2)){
        cout << ULNflows::isap(s, t, n+2) << endl;
    }else{
        cout << "-1";
    }
}