Login
Register
Problem list
Online status
09022332王昱翔
:
2024-05-15 12:43:22
#include
#include
#include
#include
using namespace std; struct Edge { int v; // 目标节点 int cap; // 容量 int cost; // 费用 int rev; // 反向边的索引 }; class MinCostMaxFlow { public: int V; // 节点数量 vector
> 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
& prev, vector
& dist) { prev.assign(V, -1); dist.assign(V, INT_MAX); dist[source] = 0; priority_queue
, vector
>, greater
>> 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
minCostMaxFlow(int source, int sink) { int flow = 0; int cost = 0; vector
prev(V); vector
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
result = flowGraph.minCostMaxFlow(source, sink); cout << result.first << " " << result.second << endl; } return 0; }
1318934611
:
2023-06-10 15:12:06
#include
#include
#include
#include
using namespace std; struct Edge { int v; // 目标节点 int cap; // 容量 int cost; // 费用 int rev; // 反向边的索引 }; class MinCostMaxFlow { public: int V; // 节点数量 vector
> 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
& prev, vector
& dist) { prev.assign(V, -1); dist.assign(V, INT_MAX); dist[source] = 0; priority_queue
, vector
>, greater
>> 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
minCostMaxFlow(int source, int sink) { int flow = 0; int cost = 0; vector
prev(V); vector
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
result = flowGraph.minCostMaxFlow(source, sink); cout << result.first << " " << result.second << endl; } return 0; }
xiaogans
:
2023-06-08 12:41:09
#include
#include
#include
#include
using namespace std; struct Edge { int v; // 目标节点 int cap; // 容量 int cost; // 费用 int rev; // 反向边的索引 }; class MinCostMaxFlow { public: int V; // 节点数量 vector
> 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
& prev, vector
& dist) { prev.assign(V, -1); dist.assign(V, INT_MAX); dist[source] = 0; priority_queue
, vector
>, greater
>> 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
minCostMaxFlow(int source, int sink) { int flow = 0; int cost = 0; vector
prev(V); vector
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
result = flowGraph.minCostMaxFlow(source, sink); cout << result.first << " " << result.second << endl; } return 0; }
Post Your Comment