Comment

harkerhand: 2025-04-25 17:15:05

我从没有觉得写最大费用最小流开心过（误


#include <bits/stdc++.h>
using namespace std;

#define INF 1e9
#define MAXN 100

class MinCostMaxFlow
{
public:
    int n, source, sink;
    vector<vector<int>> adj, cost, cap;
    vector<int> dist, parent;

    MinCostMaxFlow(int n) : n(n)
    {
        adj.resize(n);
        cost.resize(n, vector<int>(n, 0));
        cap.resize(n, vector<int>(n, 0));
        dist.resize(n);
        parent.resize(n);
    }

    void addEdge(int u, int v, int c, int w)
    {
        adj[u].push_back(v);
        adj[v].push_back(u); // 添加反向边
        cap[u][v] += c;      // 正向边容量
        cap[v][u] += 0;      // 反向边初始容量为0
        cost[u][v] = w;      // 正向边费用
        cost[v][u] = -w;     // 反向边费用为负
    }

    bool spfa()
    {
        fill(dist.begin(), dist.end(), INF);
        vector<bool> in_queue(n, false);
        queue<int> q;

        dist[source] = 0;
        q.push(source);
        in_queue[source] = true;

        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            in_queue[u] = false;

            for (int v : adj[u])
            {
                if (cap[u][v] > 0 && dist[u] + cost[u][v] < dist[v])
                {
                    dist[v] = dist[u] + cost[u][v];
                    parent[v] = u;
                    if (!in_queue[v])
                    {
                        q.push(v);
                        in_queue[v] = true;
                    }
                }
            }
        }

        return dist[sink] < INF;
    }

    pair<int, int> minCostMaxFlow(int _source, int _sink)
    {
        source = _source;
        sink = _sink;

        int maxFlow = 0, minCost = 0;

        while (spfa())
        {
            int flow = INF;
            for (int v = sink; v != source; v = parent[v])
            {
                flow = min(flow, cap[parent[v]][v]);
            }
            maxFlow += flow;
            minCost += flow * dist[sink];

            for (int v = sink; v != source; v = parent[v])
            {
                cap[parent[v]][v] -= flow;
                cap[v][parent[v]] += flow; // 增加反向边容量
            }
        }

        return {maxFlow, minCost};
    }
};

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        int n, m;
        cin >> n >> m;

        MinCostMaxFlow mcmf(n + m + 2);

        int source = n + m;
        int sink = n + m + 1;

        vector<vector<int>> cost(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                cin >> cost[i][j];

        for (int i = 0; i < n; i++)
        {
            int k;
            cin >> k;
            for (int j = 0; j < k; j++)
            {
                int woman;
                cin >> woman;
                woman--; // 转为0索引
                mcmf.addEdge(i, n + woman, 1, cost[woman][i]);
            }
            mcmf.addEdge(source, i, 1, 0);
        }

        for (int i = 0; i < m; i++)
        {
            mcmf.addEdge(n + i, sink, 1, 0);
        }

        pair<int, int> result = mcmf.minCostMaxFlow(source, sink);
        cout << result.first << " " << result.second << endl;
    }

    return 0;
}

09022332王昱翔: 2024-05-15 12:43:22

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Edge {
    int v;  // 目标节点
    int cap;  // 容量
    int cost;  // 费用
    int rev;  // 反向边的索引
};

class MinCostMaxFlow {
public:
    int V;  // 节点数量
    vector<vector<Edge>> graph;  // 图的邻接表表示

    MinCostMaxFlow(int V) {
        this->V = V;
        graph.resize(V);
    }

    // 添加边
    void addEdge(int u, int v, int cap, int cost) {
        Edge forward = {v, cap, cost, graph[v].size()};
        Edge backward = {u, 0, -cost, graph[u].size()};
        graph[u].push_back(forward);
        graph[v].push_back(backward);
    }

    // Dijkstra算法找到最小费用路径
    bool dijkstra(int source, int sink, vector<int>& prev, vector<int>& dist) {
        prev.assign(V, -1);
        dist.assign(V, INT_MAX);
        dist[source] = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, source});

        while (!pq.empty()) {
            int u = pq.top().second;
            int d = pq.top().first;
            pq.pop();

            if (d > dist[u]) {
                continue;
            }

            for (int i = 0; i < graph[u].size(); i++) {
                Edge& edge = graph[u][i];
                int v = edge.v;

                if (edge.cap > 0 && dist[u] + edge.cost < dist[v]) {
                    dist[v] = dist[u] + edge.cost;
                    prev[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }

        return prev[sink] != -1;
    }

    // 计算最小费用最大流
    pair<int, int> minCostMaxFlow(int source, int sink) {
        int flow = 0;
        int cost = 0;

        vector<int> prev(V);
        vector<int> dist(V);

        while (dijkstra(source, sink, prev, dist)) {
            int f = INT_MAX;
            int v = sink;

            // 找到路径上的最小容量
            while (v != source) {
                int u = prev[v];
                int idx = -1;

                for (int i = 0; i < graph[u].size(); i++) {
                    if (graph[u][i].v == v) {
                        idx = i;
                        break;
                    }
                }

                f = min(f, graph[u][idx].cap);
                v = u;
            }

            // 更新路径上的边的容量和费用
            v = sink;
            while (v != source) {
                int u = prev[v];
                int idx = -1;

                for (int i = 0; i < graph[u].size(); i++) {
                    if (graph[u][i].v == v) {
                        idx = i;
                        break;
                    }
                }

                graph[u][idx].cap -= f;
                graph[v][graph[u][idx].rev].cap += f;
                cost += f * graph[u][idx].cost;
                v = u;
            }

            flow += f;
        }

        return {flow, cost};
    }
};

int main() {
    int T;
    cin >> T;

    for (int t = 0; t < T; t++) {
        int n, m;
        cin >> n >> m;

        MinCostMaxFlow flowGraph(n + m + 2);

        int source = 0;
        int sink = n + m + 1;

        // 构建网络模型
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int cost;
                cin >> cost;
                flowGraph.addEdge(i, m + j, 1, cost);
            }
        }

        for (int i = 1; i <= n; i++) {
            int k;
            cin >> k;
            for (int j = 0; j < k; j++) {
                int girl;
                cin >> girl;
                flowGraph.addEdge(m + i, girl, 1, 0);
            }
        }

        // 执行最小费用最大流算法
        pair<int, int> result = flowGraph.minCostMaxFlow(source, sink);

        cout << result.first << " " << result.second << endl;
    }

    return 0;
}

1318934611: 2023-06-10 15:12:06

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Edge {
    int v;  // 目标节点
    int cap;  // 容量
    int cost;  // 费用
    int rev;  // 反向边的索引
};

class MinCostMaxFlow {
public:
    int V;  // 节点数量
    vector<vector<Edge>> graph;  // 图的邻接表表示

    MinCostMaxFlow(int V) {
        this->V = V;
        graph.resize(V);
    }

    // 添加边
    void addEdge(int u, int v, int cap, int cost) {
        Edge forward = {v, cap, cost, graph[v].size()};
        Edge backward = {u, 0, -cost, graph[u].size()};
        graph[u].push_back(forward);
        graph[v].push_back(backward);
    }

    // Dijkstra算法找到最小费用路径
    bool dijkstra(int source, int sink, vector<int>& prev, vector<int>& dist) {
        prev.assign(V, -1);
        dist.assign(V, INT_MAX);
        dist[source] = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, source});

        while (!pq.empty()) {
            int u = pq.top().second;
            int d = pq.top().first;
            pq.pop();

            if (d > dist[u]) {
                continue;
            }

            for (int i = 0; i < graph[u].size(); i++) {
                Edge& edge = graph[u][i];
                int v = edge.v;

                if (edge.cap > 0 && dist[u] + edge.cost < dist[v]) {
                    dist[v] = dist[u] + edge.cost;
                    prev[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }

        return prev[sink] != -1;
    }

    // 计算最小费用最大流
    pair<int, int> minCostMaxFlow(int source, int sink) {
        int flow = 0;
        int cost = 0;

        vector<int> prev(V);
        vector<int> dist(V);

        while (dijkstra(source, sink, prev, dist)) {
            int f = INT_MAX;
            int v = sink;

            // 找到路径上的最小容量
            while (v != source) {
                int u = prev[v];
                int idx = -1;

                for (int i = 0; i < graph[u].size(); i++) {
                    if (graph[u][i].v == v) {
                        idx = i;
                        break;
                    }
                }

                f = min(f, graph[u][idx].cap);
                v = u;
            }

            // 更新路径上的边的容量和费用
            v = sink;
            while (v != source) {
                int u = prev[v];
                int idx = -1;

                for (int i = 0; i < graph[u].size(); i++) {
                    if (graph[u][i].v == v) {
                        idx = i;
                        break;
                    }
                }

                graph[u][idx].cap -= f;
                graph[v][graph[u][idx].rev].cap += f;
                cost += f * graph[u][idx].cost;
                v = u;
            }

            flow += f;
        }

        return {flow, cost};
    }
};

int main() {
    int T;
    cin >> T;

    for (int t = 0; t < T; t++) {
        int n, m;
        cin >> n >> m;

        MinCostMaxFlow flowGraph(n + m + 2);

        int source = 0;
        int sink = n + m + 1;

        // 构建网络模型
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int cost;
                cin >> cost;
                flowGraph.addEdge(i, m + j, 1, cost);
            }
        }

        for (int i = 1; i <= n; i++) {
            int k;
            cin >> k;
            for (int j = 0; j < k; j++) {
                int girl;
                cin >> girl;
                flowGraph.addEdge(m + i, girl, 1, 0);
            }
        }

        // 执行最小费用最大流算法
        pair<int, int> result = flowGraph.minCostMaxFlow(source, sink);

        cout << result.first << " " << result.second << endl;
    }

    return 0;
}

xiaogans: 2023-06-08 12:41:09

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Edge {
    int v;  // 目标节点
    int cap;  // 容量
    int cost;  // 费用
    int rev;  // 反向边的索引
};

class MinCostMaxFlow {
public:
    int V;  // 节点数量
    vector<vector<Edge>> graph;  // 图的邻接表表示

    MinCostMaxFlow(int V) {
        this->V = V;
        graph.resize(V);
    }

    // 添加边
    void addEdge(int u, int v, int cap, int cost) {
        Edge forward = {v, cap, cost, graph[v].size()};
        Edge backward = {u, 0, -cost, graph[u].size()};
        graph[u].push_back(forward);
        graph[v].push_back(backward);
    }

    // Dijkstra算法找到最小费用路径
    bool dijkstra(int source, int sink, vector<int>& prev, vector<int>& dist) {
        prev.assign(V, -1);
        dist.assign(V, INT_MAX);
        dist[source] = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, source});

        while (!pq.empty()) {
            int u = pq.top().second;
            int d = pq.top().first;
            pq.pop();

            if (d > dist[u]) {
                continue;
            }

            for (int i = 0; i < graph[u].size(); i++) {
                Edge& edge = graph[u][i];
                int v = edge.v;

                if (edge.cap > 0 && dist[u] + edge.cost < dist[v]) {
                    dist[v] = dist[u] + edge.cost;
                    prev[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }

        return prev[sink] != -1;
    }

    // 计算最小费用最大流
    pair<int, int> minCostMaxFlow(int source, int sink) {
        int flow = 0;
        int cost = 0;

        vector<int> prev(V);
        vector<int> dist(V);

        while (dijkstra(source, sink, prev, dist)) {
            int f = INT_MAX;
            int v = sink;

            // 找到路径上的最小容量
            while (v != source) {
                int u = prev[v];
                int idx = -1;

                for (int i = 0; i < graph[u].size(); i++) {
                    if (graph[u][i].v == v) {
                        idx = i;
                        break;
                    }
                }

                f = min(f, graph[u][idx].cap);
                v = u;
            }

            // 更新路径上的边的容量和费用
            v = sink;
            while (v != source) {
                int u = prev[v];
                int idx = -1;

                for (int i = 0; i < graph[u].size(); i++) {
                    if (graph[u][i].v == v) {
                        idx = i;
                        break;
                    }
                }

                graph[u][idx].cap -= f;
                graph[v][graph[u][idx].rev].cap += f;
                cost += f * graph[u][idx].cost;
                v = u;
            }

            flow += f;
        }

        return {flow, cost};
    }
};

int main() {
    int T;
    cin >> T;

    for (int t = 0; t < T; t++) {
        int n, m;
        cin >> n >> m;

        MinCostMaxFlow flowGraph(n + m + 2);

        int source = 0;
        int sink = n + m + 1;

        // 构建网络模型
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int cost;
                cin >> cost;
                flowGraph.addEdge(i, m + j, 1, cost);
            }
        }

        for (int i = 1; i <= n; i++) {
            int k;
            cin >> k;
            for (int j = 0; j < k; j++) {
                int girl;
                cin >> girl;
                flowGraph.addEdge(m + i, girl, 1, 0);
            }
        }

        // 执行最小费用最大流算法
        pair<int, int> result = flowGraph.minCostMaxFlow(source, sink);

        cout << result.first << " " << result.second << endl;
    }

    return 0;
}