Title address:

https://www.acwing.com/problem/content/2190/

Given a containing n n n points m m For a digraph with m edges, each edge has a lower bound and an upper bound. Find a feasible scheme so that all edges meet the flow limit on the premise that all points meet the flow balance condition.

Input format:
The first line contains two integers n n n and m m m. next m m m rows, each containing four integers a , b , c , d a,b,c,d a. B, C and d represent points a a a and b b There is a directed edge between b, and the lower bound of the flow of this edge is c c c. The upper bound of flow is d d d. Point number from 1 1 1 to n n n.

Output format:
If there is a feasible solution, the first line outputs YES, and then m m m lines, each line outputs an integer, where i i The integer in line i represents the number of seconds entered i i i the flow rate of each side. If there is NO feasible scheme, directly output a line of NO. If the feasible scheme is not unique, any scheme can be output.

Data range:
1 ≤ n ≤ 200 1≤n≤200 1≤n≤200
1 ≤ m ≤ 10200 1≤m≤10200 1≤m≤10200
1 ≤ a , b ≤ n 1≤a,b≤n 1≤a,b≤n
0 ≤ c ≤ d ≤ 10000 0≤c≤d≤10000 0≤c≤d≤10000

The upper and lower bound feasible flow of passive sink is also called circulating flow, which is like a certain amount of water circulating in a water pipe. Since each edge has a lower limit of capacity, it is easy to think of building a new network. Set the capacity of each edge as the difference between the upper and lower limits of the capacity of the original graph. In this way, any feasible flow in the new network must meet the capacity limit, but the flow conservation may not be met. We can adopt this method if the lower limit of the total capacity of the incoming edge c c c is greater than the lower limit of the total capacity of the outlet c ′ c' c ', then the difference can be supplemented from the source point to this point (i.e. opening a capacity line from the source point to this point is c − c ′ c-c' c − c '; On the contrary, the excess differential supply from this point to the sink point (i.e. one line from this point to the sink point) is c ′ − c c'-c c ′− c). The question of whether there is a feasible flow that meets the capacity limit is equivalent to asking whether the maximum flow in the new network can reach the sum of the outlet capacity of the source point. You can take a rough look at the corresponding relationship. For any full flow in the new network, after removing the source point and sink point (the edge connected with them), add the flow in each edge to its lower limit in the original graph to obtain a feasible flow of the original graph; For a feasible flow of the original graph, subtract the lower limit of the flow in each side from the original graph, and then add the source and sink points to compose the graph in the above way to obtain a full flow in the new network. Therefore, the problem is transformed into finding the maximum flow in the new network, which can be solved by Dinic algorithm. The code is as follows:

#include <iostream>
#include <cstring>
using namespace std;

const int N = 210, M = (10200 + N) * 2, INF = 1e8;
int n, m, S, T;
int h[N], e[M], ne[M], f[M], l[M], idx;
int q[N], d[N], cur[N], diff[N];

// Construct the residual network of the new network. The capacity of each edge is the upper lower limit
void add(int a, int b, int c, int d) {
    e[idx] = b, ne[idx] = h[a], f[idx] = d - c, l[idx] = c, h[a] = idx++;
    e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx++;
}

bool bfs() {
    memset(d, -1, sizeof d);
    
    int hh = 0, tt = 0;
    q[tt++] = S, d[S] = 0, cur[S] = h[S];
    while (hh < tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int v = e[i];
            if (d[v] == -1 && f[i]) {
                d[v] = d[t] + 1;
                if (v == T) return true;

                cur[v] = h[v];
                q[tt++] = v;
            }
        }
    }
    
    return false;
}

int dfs(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        cur[u] = i;
        int v = e[i];
        if (d[v] == d[u] + 1 && f[i]) {
            int t = dfs(v, min(limit - flow, f[i]));
            if (!t) d[v] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }

    return flow;
}

int dinic() {
    int r = 0, flow;
    while (bfs()) while(flow = dfs(S, INF)) r += flow;
    return r;
}

int main() {
    cin >> n >> m;
    S = 0, T = n + 1;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        add(a, b, c, d);
        diff[a] -= c, diff[b] += c;
    }

    int tot = 0;
    // Find the flow of full flow
    for (int i = 1; i <= n; i++)
        if (diff[i] > 0) add(S, i, 0, diff[i]), tot += diff[i];
        else if (diff[i] < 0) add(i, T, 0, -diff[i]);

	// If the maximum flow is not the flow with the full outlet edge of the source point, there is no solution, otherwise the flow is output
    if (dinic() < tot) cout << "NO" << endl;
    else {
        cout << "YES" << endl;
        for (int i = 0; i < m * 2; i += 2) 
        	// The capacity of the reverse side plus the lower limit of the residual network
            cout << f[i ^ 1] + l[i] << endl;
    }

    return 0;
}

Time complexity O ( n 2 m ) O(n^2m) O(n2m), space O ( n ) O(n) O(n).