Menu
Article ACM

ZOJ 2314 Reactor Cooling

NodeKey

NodeKey

• 3 min read

无汇源上下界可行流的模板题。
说是模板题，其实想让它除了二分以外加点变化也是有点困难的。

关于上下界网络流的问题，以前偷懒没学，本来打算这几天补上，加上今天薛昊这个催化剂又来问我，于是就今天开始补了。

在这里我非常非常非常非常非常推荐这篇博文
总结的非常详细，写的有十分通俗易懂，全文十分连贯，评论也有人说看完给人一种荡气回肠的感觉。
当我看完无汇源上下界可行流的时候，我马上敲了一蛤这道题，就一 A 了。妙啊！

下面简单说一下无汇源上下界可行流的解法，不详细说明，具体请看上面的链接。
无汇源上下界可行流可用建图+最大流解决，建图方式如下：

  • 对每个给定的边建边，容量为 up – down
  • 记录每个点的 down 流量差，这里设 入流量为正，出流量为负。如果总的流量差大于0，建边 src -> 该点，容量为流量差。否则，建边 该点 -> des 容量为流量差的负值。

没了，再跑一遍最大流，如果能满流就说明有可行流，否则无解。

题意：
无汇源上下界可行流裸题。

思路：
见上。

AC Code

#include <bits/stdc++.h>

using namespace std;

using namespace std;
const int maxn = 204;
const int maxm = 4e4 + 5;
const int inf = 0x3f3f3f3f;

int n, m, src, des, idx;
int cur[maxn], level[maxn], head[maxn];
int cap[maxm];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm];

queue<int> que;

int getNode(int a, int b) { return a * m + b; }

void addEdge(int u, int v, int c)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], 0);
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que.push(src);
    level[src] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            if (edges[id].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[des] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == des)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (edges[id].cap > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].cap)))) {
            edges[id].cap -= cflow;
            edges[id ^ 1].cap += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= des; i++)
            cur[i] = head[i];
        while ((cflow = dfs(src, inf)))
            ans += cflow;
    }
    return ans;
}

void init(int st, int en)
{
    memset(head, -1, sizeof head);
    idx = 0;
    src = st, des = en;
}

int deg[maxn], down[maxm];

int main()
{
    int T, u, v, up;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        init(0, n + 1);
        memset(deg, 0, sizeof deg);
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d %d", &u, &v, &down[i], &up);
            addEdge(u, v, up - down[i]);
            deg[u] -= down[i], deg[v] += down[i];
        }
        int sum = 0;
        for (int i = 1; i <= n; i++)
            if (deg[i] > 0) {
                addEdge(src, i, deg[i]);
                sum += deg[i];
            } else
                addEdge(i, des, -deg[i]);
        if (dinic() < sum) {
            puts("NO");
        } else {
            puts("YES");
            for (int i = 0; i < m; i++)
                printf("%d\n", edges[i << 1 | 1].cap + down[i]);
        }
    }
    return 0;
}
Share