有源汇有上下界最大/最小流

#include <bits/stdc++.h>
#define int long long
#define LL long long
#define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
inline int read() {
    int x = 0, f = 1;
    char ch;
    for (ch = getchar(); !isdigit(ch); ch = getchar())
        if (ch == '-')
            f = -f;
    for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0';
    return x * f;
}
const int maxn = 500010;
struct Dinic {
#define oo 21474832333333LL
    int n, m, s, t;
    int cur[maxn], head[maxn], nx[maxn];
    struct Edge {
        int from, to, caps;
        Edge() {}
        Edge(int _1, int _2, int _3) : from(_1), to(_2), caps(_3) {}
    } es[maxn];
    void add(int u, int v, int w) {
        es[m] = Edge(u, v, w);
        nx[m] = head[u];
        head[u] = m++;
        es[m] = Edge(v, u, 0);
        nx[m] = head[v];
        head[v] = m++;
    }
    Dinic() {
        m = 0;
        memset(head, -1, sizeof(head));
    }
    queue<int> q;
    int dis[maxn];
    int BFS() {
        for (int i = 0; i <= n; i++) dis[i] = 0;
        dis[t] = 1;
        q.push(t);
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (int i = head[now]; i != -1; i = nx[i]) {
                Edge &e = es[i ^ 1];
                if (!dis[e.from] && e.caps) {
                    dis[e.from] = dis[now] + 1;
                    q.push(e.from);
                }
            }
        }
        return (dis[s] > 1);
    }
    int DFS(int u, int a) {
        if (u == t || !a)
            return a;
        int flow = 0, f;
        for (int &i = cur[u]; i != -1; i = nx[i]) {
            Edge &e = es[i];
            if (dis[e.to] == dis[u] - 1 && (f = DFS(e.to, min(e.caps, a)))) {
                flow += f;
                a -= f;
                e.caps -= f;
                es[i ^ 1].caps += f;
                if (a == 0)
                    return flow;
            }
        }
        return flow;
    }
    int MaxFlow(int _s, int _t) {
        s = _s, t = _t;
        int flow = 0, f;
        while (BFS()) {
            for (int i = 0; i <= n; i++) cur[i] = head[i];
            while (f = DFS(s, oo)) flow += f;
        }
        return flow;
    }
} sol;
int ind[maxn];
signed main() {
    int n = read(), m = read(), s = read(), t = read(), SS = n + 1, TT = n + 2;
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read(), b = read(), a = read();
        sol.add(u, v, a - b); ind[v] += b; ind[u] -= b;
    } sol.n = n + 5;
    int totflow = 0;
    rep(u, 1, n) {
        if(ind[u] > 0) sol.add(SS, u, ind[u]), totflow += ind[u];
        if(ind[u] < 0) sol.add(u, TT, -ind[u]);
    }
    sol.add(t, s, oo);
    int rflow = sol.MaxFlow(SS, TT);
    if(totflow > rflow) {
        cout << "please go home to sleep" << endl;
        return 0;
    } sol.es[m - 1].caps = sol.es[m - 2].caps = 0;
    cout << oo - sol.MaxFlow(t, s) << endl;
}

#include <bits/stdc++.h>
#define int long long
#define LL long long
#define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
inline int read() {
    int x = 0, f = 1;
    char ch;
    for (ch = getchar(); !isdigit(ch); ch = getchar())
        if (ch == '-')
            f = -f;
    for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0';
    return x * f;
}
const int maxn = 200010;
struct Dinic {
#define oo 21474832333333LL
    int n, m, s, t;
    int cur[maxn], head[maxn], nx[maxn];
    struct Edge {
        int from, to, caps;
        Edge() {}
        Edge(int _1, int _2, int _3) : from(_1), to(_2), caps(_3) {}
    } es[maxn];
    void add(int u, int v, int w) {
        es[m] = Edge(u, v, w);
        nx[m] = head[u];
        head[u] = m++;
        es[m] = Edge(v, u, 0);
        nx[m] = head[v];
        head[v] = m++;
    }
    Dinic() {
        m = 0;
        memset(head, -1, sizeof(head));
    }
    queue<int> q;
    int dis[maxn];
    int BFS() {
        for (int i = 0; i <= n; i++) dis[i] = 0;
        dis[t] = 1;
        q.push(t);
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (int i = head[now]; i != -1; i = nx[i]) {
                Edge &e = es[i ^ 1];
                if (!dis[e.from] && e.caps) {
                    dis[e.from] = dis[now] + 1;
                    q.push(e.from);
                }
            }
        }
        return (dis[s] > 1);
    }
    int DFS(int u, int a) {
        if (u == t || !a)
            return a;
        int flow = 0, f;
        for (int &i = cur[u]; i != -1; i = nx[i]) {
            Edge &e = es[i];
            if (dis[e.to] == dis[u] - 1 && (f = DFS(e.to, min(e.caps, a)))) {
                flow += f;
                a -= f;
                e.caps -= f;
                es[i ^ 1].caps += f;
                if (a == 0)
                    return flow;
            }
        }
        return flow;
    }
    int MaxFlow(int _s, int _t) {
        s = _s, t = _t;
        int flow = 0, f;
        while (BFS()) {
            for (int i = 0; i <= n; i++) cur[i] = head[i];
            while (f = DFS(s, oo)) flow += f;
        }
        return flow;
    }
} sol;
int ind[maxn];
signed main() {
    int n = read(), m = read(), s = read(), t = read(), SS = n + 1, TT = n + 2;
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read(), b = read(), a = read();
        sol.add(u, v, a - b);
        ind[v] += b;
        ind[u] -= b;
    }
    sol.n = n + 5;
    int totflow = 0;
    rep(u, 1, n) {
        if (ind[u] > 0)
            sol.add(SS, u, ind[u]), totflow += ind[u];
        if (ind[u] < 0)
            sol.add(u, TT, -ind[u]);
    }
    sol.add(t, s, oo);
    int rflow = sol.MaxFlow(SS, TT);
    if (totflow > rflow) {
        cout << "please go home to sleep" << endl;
        return 0;
    }
    sol.es[m - 1].caps = sol.es[m - 2].caps = 0;
    cout << sol.MaxFlow(s, t) << endl;
}