ZOJ 2314 Reactor Cooling——無源彙有上下界可行流

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int maxn = 500;
const int INF = 0x3f3f3f3f;

int n, m, s, t;
struct Edge {
    int from, to, flow, cap, up, down;
};
struct Dinic {
    vector<Edge> edges;
    vector<int> G[maxn];
    int level[maxn], cur[maxn];
    void init() {
        edges.clear();
        for (int i = 0; i < maxn; i++) G[i].clear();
    }
    void addedge(int from , int to, int cap, int up, int down) {
        edges.push_back(Edge{from, to, 0, cap, up, down});
        edges.push_back(Edge{to, from, 0, 0, up, down});
        G[from].push_back(edges.size()-2);
        G[to].push_back(edges.size()-1);
    }
    int bfs() {
        memset(level, 0, sizeof(level));
        level[s] = 1;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 0; i < G[u].size(); i++) {
                Edge &e = edges[G[u][i]];
                if (e.cap - e.flow > 0 && !level[e.to]) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t];
    }
    int dfs(int u, int f) {
        if (u == t || !f) return f;
        for (int &i = cur[u]; i < G[u].size(); i++) {
            Edge &e = edges[G[u][i]];
            if (e.cap - e.flow > 0 && level[e.to] == level[u] + 1) {
                int d = dfs(e.to, min(f, e.cap - e.flow));
                if (d > 0) {
                    e.flow += d;
                    edges[G[u][i]^1].flow -= d;
                    return d;
                }
            }
        }
        return 0;
    }
    int maxflow() {
        int ans = 0, f;
        while (bfs()) {
            memset(cur, 0, sizeof(cur));
            while ((f = dfs(s, INF))) ans += f;
        }
        return ans;
    }
}ac;

int A[maxn];

int main() {
    int N;
    scanf("%d", &N);
    for (int kase = 1; kase <= N; kase++) {
        scanf("%d%d", &n, &m);
        s = 0, t = n+1;
        ac.init();
        memset(A, 0, sizeof(A));
        for (int i = 0; i < m; i++) {
            int d1, d2, d3, d4;
            scanf("%d%d%d%d", &d1, &d2, &d3, &d4);
            ac.addedge(d1, d2, d4 - d3, d4, d3);
            A[d1] -= d3;
            A[d2] += d3;
        }
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (A[i] < 0) {
                ac.addedge(i, t, -A[i], 0, 0);
                sum -= A[i];
            }
            else {
                ac.addedge(s, i, A[i], 0, 0);
            }
        }
        int ans = ac.maxflow();
        if (kase != 1) printf("\n");
        if (ans == sum) {
            printf("YES\n");
            for (int i = 0, j = 0; j < m; i += 2, j++) {
                printf("%d\n", ac.edges[i].flow + ac.edges[i].down);
            }
        }
        else {
            printf("NO\n");
        }
    }
    return 0;
}