fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Cấu trúc cạnh trong mạng luồng
  5. struct Edge {
  6.     int to;        // Đỉnh đích
  7.     int rev;       // Vị trí ngược trong danh sách cạnh của đỉnh 'to'
  8.     int capacity;  // Sức chứa
  9.     long long cost;    // Chi phí
  10. };
  11.  
  12. // Hàm thêm cạnh vào mạng luồng
  13. void add_edge(vector<vector<Edge>> &graph, int from, int to, int capacity, long long cost){
  14.     Edge a = {to, (int)graph[to].size(), capacity, cost};
  15.     Edge b = {from, (int)(graph[from].size()), 0, -cost};
  16.     graph[from].push_back(a);
  17.     graph[to].push_back(b);
  18. }
  19.  
  20. // Hàm tính Min-Cost Max-Flow sử dụng thuật toán SPFA
  21. pair<long long, long long> min_cost_flow(vector<vector<Edge>> &graph, int S, int T){
  22.     int n = graph.size();
  23.     long long flow = 0, cost = 0;
  24.     vector<long long> prevv(n, -1);
  25.     vector<long long> preve(n, -1);
  26.  
  27.     while(1){
  28.         // Tìm đường đi có chi phí ngắn nhất từ S đến T
  29.         vector<long long> dist(n, 1e18);
  30.         vector<bool> inqueue(n, false);
  31.         dist[S] = 0;
  32.         queue<int> q;
  33.         q.push(S);
  34.         inqueue[S] = true;
  35.  
  36.         while(!q.empty()){
  37.             int u = q.front(); q.pop();
  38.             inqueue[u] = false;
  39.             for(int i=0;i<graph[u].size();i++){
  40.                 Edge &e = graph[u][i];
  41.                 if(e.capacity >0 && dist[e.to] > dist[u] + e.cost){
  42.                     dist[e.to] = dist[u] + e.cost;
  43.                     prevv[e.to] = u;
  44.                     preve[e.to] = i;
  45.                     if(!inqueue[e.to]){
  46.                         q.push(e.to);
  47.                         inqueue[e.to] = true;
  48.                     }
  49.                 }
  50.             }
  51.         }
  52.  
  53.         if(dist[T] == 1e18) break; // Không còn đường đi
  54.  
  55.         // Tìm lượng luồng tăng thêm
  56.         long long d = 1e18;
  57.         int v = T;
  58.         while(v != S){
  59.             int u = prevv[v];
  60.             int idx = preve[v];
  61.             d = min(d, (long long)graph[u][idx].capacity);
  62.             v = u;
  63.         }
  64.  
  65.         flow += d;
  66.         cost += d * dist[T];
  67.         v = T;
  68.         while(v != S){
  69.             int u = prevv[v];
  70.             int idx = preve[v];
  71.             graph[u][idx].capacity -= d;
  72.             graph[v][graph[u][idx].rev].capacity += d;
  73.             v = u;
  74.         }
  75.     }
  76.     return {flow, cost};
  77. }
  78.  
  79. int main(){
  80.     ios::sync_with_stdio(false);
  81.     cin.tie(0);
  82.  
  83.     int k, n, m;
  84.     cin >> k >> n >> m;
  85.  
  86.     // Đọc trọng số a[i] và b[i]
  87.     vector<pair<int, int>> clusters(k);
  88.     for(int i=0;i<k;i++) cin >> clusters[i].first >> clusters[i].second;
  89.  
  90.     // Định nghĩa các đỉnh trong mạng luồng
  91.     // 0: Source (S)
  92.     // 1 đến k: Cụm dữ liệu
  93.     // k+1: Nhóm loại 1
  94.     // k+2: Nhóm loại 2
  95.     // k+3: Sink (T)
  96.     int S = 0;
  97.     int T = k + 3;
  98.     int group1 = k + 1;
  99.     int group2 = k + 2;
  100.     int total_nodes = k + 4;
  101.  
  102.     vector<vector<Edge>> graph(total_nodes, vector<Edge>());
  103.  
  104.     // Thêm cạnh từ S đến từng cụm dữ liệu
  105.     for(int i=0;i<k;i++){
  106.         add_edge(graph, S, 1+i, 1, 0); // capacity 1, cost 0
  107.     }
  108.  
  109.     // Thêm cạnh từ cụm dữ liệu đến nhóm loại 1 và nhóm loại 2
  110.     for(int i=0;i<k;i++){
  111.         // Chi phí là -a[i] để tối đa hóa tổng a[i] khi chọn vào nhóm 1
  112.         add_edge(graph, 1+i, group1, 1, - (long long)clusters[i].first);
  113.         // Chi phí là -b[i] để tối đa hóa tổng b[i] khi chọn vào nhóm 2
  114.         add_edge(graph, 1+i, group2, 1, - (long long)clusters[i].second);
  115.     }
  116.  
  117.     // Thêm cạnh từ nhóm loại 1 và nhóm loại 2 đến T
  118.     add_edge(graph, group1, T, n, 0); // capacity n, cost 0
  119.     add_edge(graph, group2, T, m, 0); // capacity m, cost 0
  120.  
  121.     // Tính luồng và chi phí
  122.     pair<long long, long long> result = min_cost_flow(graph, S, T);
  123.  
  124.     // Tổng trọng số tối đa là - chi phí
  125.     cout << -result.second;
  126. }
  127.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
4 2 1
4 9
3 5
7 2
5 5
stdout
copy 
21
https://ideone.com/1Tds7h
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!