loj116_有源汇有上下界最大流

只需把上下界最小流跑的残量网络最大流起始点换成$s->t$，和可行流相加即可。

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

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)
{
    if (u == en)
        return flow;
    long long r = flow;
    for (int eg = cur[u]; eg && r; eg = e[eg].nxt)
    {
        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));
            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);
    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(s, t));
    }
    else
        puts("please go home to sleep");
    return 0;
}