09.2 - Min Cost Flow với chi phí không âm

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e4 + 10;//Giới hạn số đỉnh

const int INF_COST = 0X3f3f3f3f; // Giá trị lớn cho chi phí (dist, hay cost)

const int INF_FLOW = 0x3f3f3f3f; // Giá trị lớn cho luồng (flow)

int head[maxn];

int dis[maxn];      // Khoảng cách (dijkstra distance)

int h[maxn];        // Potential Function (h)

int flow_limit[maxn]; // Luồng tối đa có thể đẩy đến đỉnh này

int pre[maxn];      // Đỉnh trước đó trên đường đi

int last[maxn];     // Chỉ số cạnh trước đó trên đường đi

int tot;            // Tổng số cạnh đã thêm

int n, m, s, t;     // Số đỉnh, số cạnh, Nguồn, Đích

// Khai báo cạnh

struct node{

1. int to;

2. int next;

3. int f; // Capacity (khả năng)

4. int w; // Cost (chi phí)

5. node() {}

6. node(int a, int b, int c, int d) : to(a), next(b), f(c), w(d) {}

}edge[maxn * 10]; // 5e4 * 10 = 500,000 cạnh, đủ cho 5e4 đỉnh.

// Thêm cạnh

void edgeadd(int a, int b, int c, int d){

1. edge[tot] = node(b, head[a], c, d);

2. head[a] = tot++;

3. edge[tot] = node(a, head[b], 0, -d); // Cung ngược với chi phí âm

4. head[b] = tot++;

}

// Khởi tạo đồ thị

void init(){

1. memset(head, -1, sizeof(head));

2. tot = 0;

}

// Khởi tạo các mảng cho tìm đường đi ngắn nhất

void path_init(){

1. // dis: khoảng cách (chi phí)

2. // flow_limit: luồng tối đa có thể qua

3. memset(dis, 0X3f, sizeof(dis));

4. memset(flow_limit, 0X3f, sizeof(flow_limit));

}

// ----------------------------------------------------

// Bước 1: Khởi tạo Potential Function (dùng SPFA cho lần đầu)

// Cần chạy SPFA lần đầu để tính h[] ban đầu.

// Hàm này là bắt buộc nếu muốn dùng Dijkstra sau đó.

// ----------------------------------------------------

bool initial_spfa() {

    // Chỉ dùng cho lần đầu để tính h[] (potential)

    memset(dis, 0X3f, sizeof(dis));

    memset(h, 0, sizeof(h)); // Khởi tạo h[i] = 0

    memset(last, -1, sizeof(last));

    // Sử dụng mảng vis[] để kiểm tra chu trình âm

    vector<int> cnt(n + 1, 0); // Đếm số lần đỉnh được push vào queue

    vector<bool> vis(n + 1, false);

    queue<int> q;

    q.push(s);

    dis[s] = 0;

    vis[s] = true;

    while (!q.empty()) {

        int u = q.front();

        q.pop();

        vis[u] = false;

        for (int i = head[u]; i != -1; i = edge[i].next) {

            int v = edge[i].to;

            int w = edge[i].w;

            int f = edge[i].f;

            if (f > 0 && dis[v] > dis[u] + w) {

                dis[v] = dis[u] + w;

                cnt[v]++;

                if (cnt[v] > n) {

                    // Phát hiện chu trình âm (lỗi logic nếu bài toán không cho phép)

                    return false; 

                }

                if (!vis[v]) {

                    q.push(v);

                    vis[v] = true;

                }

            }

        }

    }

    // Gán kết quả dis[] thành h[] ban đầu

    for(int i = 1; i <= n; i++) h[i] = dis[i];

    return true;

}

// ----------------------------------------------------

// Bước 2: Tìm đường ngắn nhất bằng Dijkstra + Potential

// ----------------------------------------------------

bool dijkstra(){

1. path_init();

2. // pair<re-weighted cost, node>

3. priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

4. 
   

5. dis[s] = 0;

6. flow_limit[s] = INF_FLOW;

7. pq.push({0, s});

8. 
   

9. while(!pq.empty()){

   1. int d = pq.top().first;

   2. int u = pq.top().second;

   3. pq.pop();

   4. 
      

   5. if (d > dis[u]) continue; // Đã tìm thấy đường đi ngắn hơn

   6. 
      

   7. for(int i = head[u]; i != -1; i = edge[i].next){

      1. int v = edge[i].to;

      2. int w = edge[i].w; // Chi phí gốc

      3. int f = edge[i].f;

      4. 
         

      5. // Chi phí tái định trọng số (Reduced Cost): c'(u, v) = c(u, v) + h(u) - h(v)

      6. int reduced_cost = w + h[u] - h[v];

      7. 
         

      8. if(f > 0 && dis[v] > dis[u] + reduced_cost){

         1. dis[v] = dis[u] + reduced_cost;

         2. flow_limit[v] = min(flow_limit[u], f);

         3. pre[v] = u;

         4. last[v] = i;

         5. pq.push({dis[v], v});

      9. }

   8. }

10. }

11. 
    

12. if (dis[t] == INF_COST) return false; // Không còn đường đi

13. 
    

14. // Cập nhật Potential Function cho lần lặp tiếp theo

15. // h'[v] = h[v] + dis[v]

16. for(int i = 1; i <= n; i++){

    1. if(dis[i] != INF_COST){

       1. h[i] += dis[i];

    2. }

17. }

18. 
    

19. return true;

}

// ----------------------------------------------------

// Min Cost Max Flow

// ----------------------------------------------------

void dinic(){

1. int maxflow = 0; 

2. long long minw = 0; // Chi phí

3. 
   

4. // Bước 1: Khởi tạo Potential

    if (!initial_spfa()) {

        // Xử lý chu trình âm

        cout << "Chu trinh am trong do thi goc." << endl;

        return;

    }

1. // Lặp lại tìm đường ngắn nhất (theo chi phí) và đẩy luồng

2. while(dijkstra()){

        // Luồng được đẩy qua đường đi ngắn nhất về chi phí

1.     int push_flow = flow_limit[t];

        // Chi phí thực tế của đường đi: chi phí tái định trọng số + h[t] - h[s]

        // Vì h[t] - h[s] đã được đưa vào dis[t] khi cập nhật h[]

        // Chi phí thực tế = (dis[t] ban đầu) + (h[t] - h[s])

        // Tuy nhiên, cách đơn giản nhất là tính tổng chi phí gốc trên các cạnh.

        long long current_cost = 0;

        // Tăng luồng

1.     maxflow += push_flow;

        // Đẩy luồng trên đường đi

2. 1. int x = t;

   2. while(x != s){

            int edge_id = last[x];

            current_cost += (long long)push_flow * edge[edge_id].w;

2. 2. 1. edge[edge_id].f -= push_flow; // Giảm luồng cung xuôi

      2. edge[(edge_id ^ 1)].f += push_flow; // Tăng luồng cung ngược

      3. x = pre[x];

   3. }

        minw += current_cost;

1. }

2. // Output: maxflow minw

3. cout << maxflow << " " << minw << endl;

}

int main(){

1. ios::sync_with_stdio(false);

2. cin.tie(NULL); 

3. cin >> n >> m >> s >> t;

4. init(); // Khởi tạo head[] và tot

5. 
   

6. for(int i = 1; i <= m; i++){

   1. int a, b, c, d; // a, b: đỉnh; c: khả năng (f); d: chi phí (w)

   2. cin >> a >> b >> c >> d;

   3. edgeadd(a, b, c, d);

7. }

8. 
   

9. dinic(); // Min Cost Max Flow

10. return 0;

}