费用流经典题目,我用的ZKW算法,指针存图

思路

  • 设超级源点为$0$,超级汇点为$n + m + 1$进行建图
  • 对于$\forall i \in [1, m]$,从$0$向$i$建立容量为$a_i$,费用$0$的边
  • 对于$\forall j \in [1, n]$,从$m + j$向$n + m + 1$建立容量为$b_i$,费用$0$的边
  • 对于$\forall i \in [1, m], \forall j \in [1, n]$,从$i$向$m + j$建立容量为$\infty$,费用$c_{i, j}$的边

然后跑最小费用最大流和最大费用最大流即可

程序实现

按照上面的思路,代码如下

// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <deque>

using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int m, n;

struct Edge{
    int to, val, cost;
    Edge *next, *ops;
    Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
};

namespace Zkw1{
    Edge *head[MAXN << 1], *cur[MAXN << 1];
    bool vis[MAXN << 1];
    int dis[MAXN << 1];
    int s, t, res ,ans;

    void AddEdge(int u, int v, int w, int c) {
        head[u] = new Edge(v, w, c, head[u]);
        head[v] = new Edge(u, 0, -c, head[v]);
        head[u]->ops = head[v]; head[v]->ops = head[u];
    }

    bool Spfa() {
        memset(dis, INF, sizeof(dis));
        memset(vis, false, sizeof(vis));
        deque<int> q; q.push_back(s); vis[s] = true; dis[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop_front();
            vis[u] =false;
            for (Edge *e = head[u]; e; e = e->next) {
                int v = e->to;
                if (e->val > 0 && dis[u] + e->cost < dis[v]) {
                    dis[v] = dis[u] + e->cost;
                    if (!vis[v]) {
                        vis[v] = true;
                        if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
                        else q.push_back(v);
                    }
                }
            }
        }
        return dis[t] < INF;
    }

    int Dfs(int u, int flow) {
        vis[u] = true;
        if (u == t) {
            res += flow;
            return flow;
        }
        int used = 0;
        for (Edge *&e = cur[u]; e; e = e->next) {
            int v = e->to;
            if ((v == t || !vis[v]) && e->val > 0 && dis[v] == dis[u] + e->cost) {
                int mi = Dfs(v, min(e->val, flow - used));
                if (mi) {
                    used += mi;
                    e->val -= mi;
                    e->ops->val += mi;
                    ans += e->cost * mi;
                }
                if (used == flow) break;
            }
        }
        return used;
    }

    void Work() {
        res = ans = 0;
        while (Spfa()) {
            vis[t] = true;
            while (vis[t]) {
                memset(vis, false, sizeof(vis));
                memcpy(cur, head, sizeof(head));
                Dfs(s, INF);
            }
        }
    }
}

namespace Zkw2{
    Edge *head[MAXN << 1], *cur[MAXN << 1];
    bool vis[MAXN << 1];
    int dis[MAXN << 1];
    int s, t, res ,ans;

    void AddEdge(int u, int v, int w, int c) {
        head[u] = new Edge(v, w, c, head[u]);
        head[v] = new Edge(u, 0, -c, head[v]);
        head[u]->ops = head[v]; head[v]->ops = head[u];
    }

    bool Spfa() {
        //memset(dis, -INF, sizeof(dis));
        for (int i = 1; i <= 2 * n + 1; i++) dis[i] = -INF;
        memset(vis, false, sizeof(vis));
        deque<int> q; q.push_back(s); vis[s] = true; dis[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop_front();
            vis[u] =false;
            for (Edge *e = head[u]; e; e = e->next) {
                int v = e->to;
                if (e->val > 0 && dis[u] + e->cost > dis[v]) {
                    dis[v] = dis[u] + e->cost;
                    if (!vis[v]) {
                        vis[v] = true;
                        if (!q.empty() && dis[v] > dis[q.front()]) q.push_front(v);
                        else q.push_back(v);
                    }
                }
            }
        }
        return dis[t] > -INF;
    }

    int Dfs(int u, int flow) {
        vis[u] = true;
        if (u == t) {
            res += flow;
            return flow;
        }
        int used = 0;
        for (Edge *&e = cur[u]; e; e = e->next) {
            int v = e->to;
            if ((v == t || !vis[v]) && e->val > 0 && dis[v] == dis[u] + e->cost) {
                int mi = Dfs(v, min(e->val, flow - used));
                if (mi) {
                    used += mi;
                    e->val -= mi;
                    e->ops->val += mi;
                    ans += e->cost * mi;
                }
                if (used == flow) break;
            }
        }
        return used;
    }

    void Work() {
        res = ans = 0;
        while (Spfa()) {
            vis[t] = true;
            while (vis[t]) {
                memset(vis, false, sizeof(vis));
                memcpy(cur, head, sizeof(head));
                Dfs(s, INF);
            }
        }
    }
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> m >> n;
    Zkw1 :: s = Zkw2 :: s = 0; Zkw1 :: t = Zkw2 :: t = m + n + 1;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        Zkw1 :: AddEdge(0, i, x, 0);
        Zkw2 :: AddEdge(0, i, x, 0);
    }
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        Zkw1 :: AddEdge(m + i, m + n + 1, x, 0);
        Zkw2 :: AddEdge(m + i, m + n + 1, x, 0);
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            Zkw1 :: AddEdge(i, m + j, INF, x);
            Zkw2 :: AddEdge(i, m + j, INF, x);
        }
    }
    Zkw1 :: Work(); Zkw2 :: Work();
    cout << Zkw1 :: ans << endl << Zkw2 :: ans << endl;
    return 0;
}

你开开心心复制粘贴提交,发现只有$45$分。这时需要一个技巧:第二遍把费用取相反数存跑最小费用,要比正常存图跑最大费用快。代码如下:

// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <deque>

using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int m, n;

struct Edge{
    int to, val, cost;
    Edge *next, *ops;
    Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
};

namespace Zkw1{
    Edge *head[MAXN << 1];
    bool vis[MAXN << 1];
    int dis[MAXN << 1];
    int s, t, res ,ans;

    void AddEdge(int u, int v, int w, int c) {
        head[u] = new Edge(v, w, c, head[u]);
        head[v] = new Edge(u, 0, -c, head[v]);
        head[u]->ops = head[v]; head[v]->ops = head[u];
    }

    bool Spfa() {
        memset(dis, INF, sizeof(dis));
        memset(vis, false, sizeof(vis));
        deque<int> q; q.push_back(s); vis[s] = true; dis[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop_front();
            vis[u] =false;
            for (Edge *e = head[u]; e; e = e->next) {
                int v = e->to;
                if (e->val > 0 && dis[u] + e->cost < dis[v]) {
                    dis[v] = dis[u] + e->cost;
                    if (!vis[v]) {
                        vis[v] = true;
                        if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
                        else q.push_back(v);
                    }
                }
            }
        }
        return dis[t] < INF;
    }

    int Dfs(int u, int flow) {
        vis[u] = true;
        if (u == t) {
            res += flow;
            return flow;
        }
        int used = 0;
        for (Edge *e = head[u]; e; e = e->next) {
            int v = e->to;
            if ((v == t || !vis[v]) && e->val > 0 && dis[v] == dis[u] + e->cost) {
                int mi = Dfs(v, min(e->val, flow - used));
                if (mi) {
                    used += mi;
                    e->val -= mi;
                    e->ops->val += mi;
                    ans += e->cost * mi;
                }
                if (used == flow) break;
            }
        }
        return used;
    }

    void Work() {
        res = ans = 0;
        while (Spfa()) {
            vis[t] = true;
            while (vis[t]) {
                memset(vis, false, sizeof(vis));
                Dfs(s, INF);
            }
        }
    }
}

namespace Zkw2{
    Edge *head[MAXN << 1];
    bool vis[MAXN << 1];
    int dis[MAXN << 1];
    int s, t, res ,ans;

    void AddEdge(int u, int v, int w, int c) {
        head[u] = new Edge(v, w, c, head[u]);
        head[v] = new Edge(u, 0, -c, head[v]);
        head[u]->ops = head[v]; head[v]->ops = head[u];
    }

    bool Spfa() {
        memset(dis, INF, sizeof(dis));
        memset(vis, false, sizeof(vis));
        deque<int> q; q.push_back(s); vis[s] = true; dis[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop_front();
            vis[u] =false;
            for (Edge *e = head[u]; e; e = e->next) {
                int v = e->to;
                if (e->val > 0 && dis[u] + e->cost < dis[v]) {
                    dis[v] = dis[u] + e->cost;
                    if (!vis[v]) {
                        vis[v] = true;
                        if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
                        else q.push_back(v);
                    }
                }
            }
        }
        return dis[t] < INF;
    }

    int Dfs(int u, int flow) {
        vis[u] = true;
        if (u == t) {
            res += flow;
            return flow;
        }
        int used = 0;
        for (Edge *e = head[u]; e; e = e->next) {
            int v = e->to;
            if ((v == t || !vis[v]) && e->val > 0 && dis[v] == dis[u] + e->cost) {
                int mi = Dfs(v, min(e->val, flow - used));
                if (mi) {
                    used += mi;
                    e->val -= mi;
                    e->ops->val += mi;
                    ans += e->cost * mi;
                }
                if (used == flow) break;
            }
        }
        return used;
    }

    void Work() {
        res = ans = 0;
        while (Spfa()) {
            vis[t] = true;
            while (vis[t]) {
                memset(vis, false, sizeof(vis));
                Dfs(s, INF);
            }
        }
    }
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> m >> n;
    Zkw1 :: s = Zkw2 :: s = 0; Zkw1 :: t = Zkw2 :: t = m + n + 1;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        Zkw1 :: AddEdge(0, i, x, 0);
        Zkw2 :: AddEdge(0, i, x, 0);
    }
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        Zkw1 :: AddEdge(m + i, m + n + 1, x, 0);
        Zkw2 :: AddEdge(m + i, m + n + 1, x, 0);
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            Zkw1 :: AddEdge(i, m + j, INF, x);
            Zkw2 :: AddEdge(i, m + j, INF, -x);
        }
    }
    Zkw1 :: Work(); Zkw2 :: Work();
    cout << Zkw1 :: ans << endl << -Zkw2 :: ans << endl;
    return 0;
}