Comment

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;
}