HDU 3157：Crazy Circuits - 有源匯上下界最小流

問題描述

電路板有 N 個接線柱（1~N）和兩個電源接線柱（+、-）。給定 M 條線路，每條有下限流量。求使所有元件正常工作的最小總電流（即從 + 到 - 的最小流量），無解輸出 "impossible"。

建模：有源匯上下界最小流

1. 按無源匯上下界建圖：每條邊容量 = 上限 - 下限，並計算各點需求 du[v] += lower, du[u] -= lower。
2. 添加超級源 SS 和超級匯 TT：du>0 連 SS→v 容量 du；du<0 連 v→TT 容量 -du。
3. 跑一次 SS→TT 最大流，若不滿流則無可行流。
4. 加入原匯→原源 t→s 容量 INF 的邊，再跑一次 SS→TT。若滿流，則 t→s 邊的流量即為最小流值。

參考代碼 (C++，Dinic 實現)

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN = 65, MAXE = 10005;
const int INF = 0x3f3f3f3f;

struct Edge { int u, v, cap, flow; };
struct Dinic {
    int n, m, s, t;
    Edge e[MAXE];
    int first[MAXN], nxt[MAXE];
    bool vis[MAXN]; int d[MAXN], cur[MAXN];

    void init(int n) { this->n = n; memset(first, -1, sizeof(first)); m = 0; }
    void addEdge(int u, int v, int cap) {
        e[m] = {u, v, cap, 0}; nxt[m] = first[u]; first[u] = m++;
        e[m] = {v, u, 0, 0};   nxt[m] = first[v]; first[v] = m++;
    }
    bool bfs() {
        memset(vis, 0, sizeof(vis));
        queue<int> q; q.push(s); d[s] = 0; vis[s] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = first[u]; ~i; i = nxt[i]) {
                Edge &ed = e[i];
                if (!vis[ed.v] && ed.cap > ed.flow) {
                    vis[ed.v] = 1; d[ed.v] = d[u] + 1; q.push(ed.v);
                }
            }
        }
        return vis[t];
    }
    int dfs(int u, int a) {
        if (u == t || a == 0) return a;
        int flow = 0, f;
        for (int &i = cur[u]; ~i; i = nxt[i]) {
            Edge &ed = e[i];
            if (d[u] + 1 == d[ed.v] && (f = dfs(ed.v, min(a, ed.cap - ed.flow))) > 0) {
                ed.flow += f; e[i^1].flow -= f; flow += f; a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }
    int maxflow(int s, int t) {
        this->s = s; this->t = t;
        int flow = 0;
        while (bfs()) {
            for (int i = 0; i < n; ++i) cur[i] = first[i];
            flow += dfs(s, INF);
        }
        return flow;
    }
    bool fullFlow(int ss) {
        for (int i = first[ss]; ~i; i = nxt[i])
            if (e[i].flow != e[i].cap) return false;
        return true;
    }
} gao;

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2 && (n || m)) {
        int s = 0, t = n + 1, ss = n + 2, tt = n + 3;
        gao.init(n + 4);
        int du[65] = {0};
        for (int i = 0; i < m; ++i) {
            char c1[10], c2[10]; int w;
            scanf("%s%s%d", c1, c2, &w);
            int u = (c1[0] == '+') ? s : atoi(c1);
            int v = (c2[0] == '-') ? t : atoi(c2);
            gao.addEdge(u, v, INF);
            du[u] -= w; du[v] += w;
        }
        for (int i = s; i <= t; ++i) {
            if (du[i] > 0) gao.addEdge(ss, i, du[i]);
            if (du[i] < 0) gao.addEdge(i, tt, -du[i]);
        }
        gao.maxflow(ss, tt);
        gao.addEdge(t, s, INF);
        gao.maxflow(ss, tt);
        if (!gao.fullFlow(ss)) puts("impossible");
        else printf("%d\n", gao.e[gao.m - 2].flow); // t->s 邊的流量
    }
    return 0;
}

關鍵點

• 上下界轉換：容量 = 上限 - 下限，節點需求平衡。
• 超級源匯構造可行流，再加 t→s 求最小流。
• Dinic 算法適用於稠密圖，此處 N ≤ 60 足夠。