Luồng Cực đại - Tuoitrekthc

1.     Mạng

Một đa đồ thị có hướng, không khuyên, có một đỉnh phát, một đỉnh thu và có hàm c ánh xạ từ tập cung vào tập số thực không âm tạo thành một mạng. Ký hiệu mạng G là bộ năm (V, E, c, s, t) trong đó V là tập đỉnh, E là tập cung, s là đỉnh phát, t là đỉnh thu, c: E→[0;+∞) cho tương ứng mỗi cung e với số không âm c(e) gọi là sức chứa trên cung e.

2.     Luồng

Luồng trên mạng G(V, E, c, s, t) là một hàm f ánh xạ từ tập cung E vào tập số thực: f: E→(-∞; +∞) mà thỏa mãn 3 ràng buộc sau đây:

• Trên mọi cung e: f(e) ≤ c(e), ở đây f(e) là luồng trên cung e.
• Trên mọi cung e: f(e) = – f(-e) trong đó qui ước cung -e là cung ngược chiều của cung e.
• Tại mọi đỉnh v khác s và t, tổng luồng trên các cung đi ra khỏi v bằng 0.

Từ 3 ràng buộc trên có thể suy ra: Tại mọi đỉnh v khác s và t, tổng luồng trên các cung đi vào v cũng bằng 0.

Giá trị của một luồng là tổng luồng trên các cung đi ra khỏi đỉnh phát s.

3.      Luồng dương

Luồng dương trên mạng G(V, E, c, s, t) là một hàm φ ánh xạ từ tập cung E vào tập số thực: φ: E→[0; +∞) mà thỏa mãn 2 ràng buộc sau đây:

• Trên mọi cung e: 0≤φ(e) ≤ c(e)
• Tại mọi đỉnh v khác s và t, tổng luồng trên các cung đi ra khỏi v=tổng luồng trên các cung đi vào v.

Giá trị của luồng dương bằng tổng luồng này trên các cung đi ra khỏi đỉnh phát trừ đi tổng luồng này trên các cung đi vào đỉnh phát.

Hệ quả. Giá trị của luồng dương bằng tổng luồng này trên các cung đi vào đỉnh thu trừ đi tổng luồng này trên các cung ra khỏi đỉnh thu.

Các cung e nếu có f(e)=c(e) thì gọi e là cung bão hòa, cung e có f(e)<c(e) gọi là cung thặng dư (có thể cho luồng tăng trên cung này một lượng tối đa là cf(e)=c(e)-f(e))

4.     Đường tăng luồng

Đường tăng luồng là đường đi đơn từ đỉnh s đến đỉnh t, chỉ gồm các cung thặng dư. Giá trị tăng luồng trên đường tăng luồng là giá trị nhỏ nhất của c(e)-f(e) trên các cung e thuộc đường tăng luồng (chung cho cả cung thuận và cung ngược trên đường tăng luồng).

5.     Bài toán luồng cực đại

Bài toán luồng cực đại là:

Cho một mạng G, hãy tìm luồng có giá trị lớn nhất trên mạng.

a) Thuật toán Ford-Fulkerson:

• Xuất phát từ một luồng f tùy ý trên mạng (thường chọn là f(e)=0 với mọi cung e).
• Lặp {
  • Tìm đường tăng luồng (và tìm có giá trị tăng luồng tại các đỉnh v là ∆(v)=min{∆(u), C[u,v]-f[u][v]}) với mọi cung (u;v) trên đường tăng luồng.
  • Tăng luồng f = f+∆(t) trên các cung của đường tăng luồng, đồng thời giảm giá trị luồng trên các cung đối một lượng ∆(t).

} cho đến khi không tìm được đường tăng luồng.

Thuật toán Ford-Fulkerson với kỹ thuật tìm đường tăng luồng bằng BFS gọi là thuật toán Edmonds-Karp có thời gian thực hiện là O(|V|.|E|2):

Chương trình 1. Dùng ma trận trọng số trên đồ thị thặng dư (đồ thị gồm các cung thặng dư, luôn biến động vì các cung thặng dư sau mỗi lần tăng luồng lại cập nhật giá trị mới)

 #include <iostream>

#include <fstream>

#include <queue>

#define maxN 100

using namespace std;

ifstream fi (“MAXFLOW1.INP”);

ofstream fo (“MAXFLOW1.OUT”);

int n, m, s, t;

int G[maxN][maxN];  // Đồ thị ban đầu

int rG[maxN][maxN]; // Đồ thị gồm các cung thặng dư

int parent[maxN];

bool bfs(){  // Tìm đường tăng luồng bằng BFS

    bool visited[maxN];

    memset(visited, 0, sizeof(visited)); // Đánh dấu các đỉnh chưa thăm

    queue <int> q;  // Hàng đợi để tìm các đỉnh của đường tăng luồng

    q.push(s);  // Nạp đỉnh phát s vào hàng đợi

    visited[s] = true; // Đã thăm s

    parent[s] = -1; // Đỉnh trước đỉnh s coi như -1

    while (!q.empty()) { // Trong khi hàng đợi chưa đầy, còn tìm kiếm BFS

        int u = q.front();// Lấy một đỉnh ở đầu hàng đợi

        q.pop();// Xóa đỉnh ở đầu hàng đợi

        for (int v=0; v<n; v++){ // Xét các đỉnh kề v : có cung (u;v)

            if (visited[v]==false && rG[u][v] > 0){ //v chưa thăm, (u;v) còn sức chứa

                q.push(v); // thì nạp v

                parent[v] = u; // Lưu vết trước v là u

                visited[v] = true; // Đánh dấu đã thăm v

            }

        }

    }

    return (visited[t] == true); // thăm được tới t thì có đường tăng luồng

}

int fordFulkerson(){// Thuật toán FordFulkenson

    int u, v;

    int max_flow = 0; // Khởi trị giá trị max luồng

    while (bfs()) { // Trong khi còn tìm được đường tăng luồng thì

        int delta = INT_MAX; // Khởi trị delta (giá trị tăng luồng trên một đường tăng luồng)

        for (v=t; v!=s; v=u){ // Lần ngược vết đường tăng luồng

            u = parent[v];

            delta = min(delta, rG[u][v]); // Cập nhật giá trị delta

        }

        for (v=t; v != s; v=u){ // Cập nhật các cung thặng dư và cung ngược

            u = parent[v];

            rG[u][v] -= delta;

            rG[v][u] += delta;

        }

        max_flow += delta; // Cập nhật max luồng

    }

    return max_flow; // Trả về max luồng

}

void read_input(){

    int i, j, w;

      fi>> n >> m >> s >> t ;

      for (int e=1; e<=m; e++){

        fi >> i >> j >> w;

             G[i][j] = w;

   }

   memmove(rG, G, sizeof(G));

}

int main(){

    read_input();   

    fo << fordFulkerson() << endl;

    for (int u=0; u<n; u++)

    for (int v=0; v<n; v++)

    if (G[u][v]-rG[u][v]>0) // Có luồng trên cung (u;v)

    fo << u << ” ” << v << ” ” << G[u][v]-rG[u][v] << endl;

    return 0;

}

 Chương trình 2. Thực hiện thuật toán Edmonds-Karp với cài đặt dữ liệu dựa vào ma trận trọng số, danh sách kề của đồ thị c ban đầu, xây dựng đồ thị luồng f và cập nhật sau mỗi lần tăng luồng:

#include <iostream>

#include <fstream>

#include<queue>

#include<vector>

#define maxN 1000 

#define INF 2147483646 

using namespace std;

ifstream fi (“MAXFLOW.INP”);

ofstream fo (“MAXFLOW.OUT”);

int c[maxN][maxN]; // Sức chứa trên các cung dưới dạng ma trận trọng số

int f[maxN][maxN]; // Luồng trên các cung

int trace[maxN];   // Lưu vết các đỉnh trên một đường tăng luồng   

vector<int> adj[maxN];// toàn bộ danh sách kề của mỗi đỉnh (mỗi danh sách là một vector)

int n, m, s, t; // Số dỉnh, số cung, đỉnh phát, đỉnh thu

 

int bfs(){// Tìm kiếm theo chiều rộng BFS để tìm các đường tăng luồng

  int delta[maxN];  // Lượng tối đa còn cho phép luồng thông qua mỗi đỉnh

  queue<int> q; // Hàng đợi dùng thực hiện BFS

  memset(trace, -1, sizeof(trace)); // Xin vùng nhớ và khởi trị mảng trace, mảng delta

  memset(delta, 0, sizeof(delta));

  q.push(s); // Nạp đỉnh phát s vào hàng đợi

  trace[s]=-2; // Đánh dấu đặc biệt đối với đỉnh phát đã thăm (bằng -2)

  delta[s]=INF; // Khởi trị khả năng luồng tối đa qua đỉnh phát là vô cùng

  while(!q.empty()) { // Trong khi hàng đợi chưa rỗng còn tìm kiếm đường tăng luồng

    int u = q.front(); q.pop();// Lấy đỉnh u tại đầu hàng đợi

    for(int i=0; i<adj[u].size(); i++) { // Duyệt các đỉnh v kề với u:  cung (u;v)

      int v = adj[u][i]; // v kề u

      if(trace[v] == -1){ // chưa thăm v, nên cung (u; v) là cung thuận

        if (c[u][v] – f[u][v] > 0) { // Còn có thể tăng luồng trên cung (u;v)

          trace[v] = u;  // Đánh dấu đã thăm v, trước v là u

          delta[v]= min(delta[u],c[u][v]-f[u][v]);// Luồng tối đa còn có thể qua v

          if(v==t) return delta[t];// Nếu v là t thì c2[t] là giá trị luồng được tăng thêm

          q.push(v); // còn không thì nạp v vào hàng đợi theo BFS

        }

      }

    }

  }

  return 0; // Không còn tìm được đường tăng luồng, trả về giá trị luồng tăng thêm bằng 0

}

int EdmondsKarp() {

  int maxFlow=0;

  while(true) { // Vòng lặp thực hiện thuật toán EdmondsKarp tìm luồng cực đại

    int flow=bfs();// giá trị luồng được tăng thêm khi tìm thấy đường tăng luồng

    if(flow==0) break; // không còn đường tăng luồng thì kết thúc

    maxFlow +=flow; // Cập nhật thêm cho giá trị luồng

    int v = t; // Lần ngược đường tăng luồng để cập nhật luồng trên các cung

    while( v != s){

      int u = trace[v];

      f[u][v] += flow; // Tăng luồng trên cung thuận

      f[v][u] -= flow; // Giảm luồng trên cung đối

      v= u;

    }

  }

  return maxFlow;

}

int main() {

  fi>> n>> m >> s >> t;   // Đọc số đỉnh, số cạnh, đỉnh phát, đỉnh thu

  for(int i=0; i< m; i++)  { // Đọc  m cung

    int u, v, w;

    fi>> u >> v >> w; // Cung (u;v) có sức chứa w

    c[u][v]= w;       // Ma trận sức chứa

    adj[u].push_back(v); // Nạp v vào danh sách các đỉnh kề của u ( từ u đi ra)

    adj[v].push_back(u); // Nạp u vào danh sách các đỉnh kề của v (đi vào v)

  }

  int maxFlow = EdmondsKarp();// Thuật toán trả về giá trị luồng cực đại

  fo<<maxFlow<<endl;    // Xuất ra output giá trị luồng cực đại

  for (int u=0; u<n; u++) // Xuất ra luồng trên các cung

  for (int v=0; v<n; v++)

  if (f[u][v]>0)

  fo << u << ” ” << v << ” ” << f[u][v] << endl;

  return 0;

}

 Chương trình 3. Tương tự chương trình 2 nhưng cài đặt đồ thị sức chứa và đồ thị luồng bằng danh sách cạnh (mảng E[2*maxM]) và danh sách các cung liên thuộc (mảng link[2*maxM] và mảng head[maxN]):

#include <iostream>

#include <fstream>

#include <queue>

#define maxN 100

#define maxM 1000

#define INF 2147483646 

using namespace std;

ifstream fi (“MAXFLOW.INP”);

ofstream fo (“MAXFLOW.OUT”);

struct T_Edge { int x; int y; int c; int f; } E[2*maxM];

int link[2*maxM], head[maxN], trace[maxN];

int N, M, s, t;

void read_input() {

     int j, u, v, capacity;

     fi >> N >> M >> s >> t;

     for (int i=1; i<=M; i++) {

         fi >> u >> v >> capacity; // Cung (u;v) có sức chứa là capacity

         E[i].x = u; E[i].y = v;  // Cung thứ i có điểm đầu là u, điểm cuối là v

         E[i].c = capacity; // Sức chứa của cung thứ i là capacity

         link[i] = head[u]; // Đặt liên kết cung thứ i vào vị trí đầu của dslt của đỉnh u

         head[u] = i; // Cung liên thuộc thứ nhất của đỉnh u là cung thứ i

         j = 2*M+1 – i;

         E[j].x = v; E[j].y = u; // Tương tự với cung –i là cung đối của cung i

         E[j].c = 0;

         link[j] = head[v];

         head[v] = j;

     }

     fi.close();

     for (int i=1; i<=2*M; i++) E[i].f=0; // Khởi trị luồng ban đầu trên các cung

}

int bfs(){

  int delta[maxN];

  queue<int> q;

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

  memset(delta, INF, sizeof(delta));

  q.push(s); // Nạp s vào hàng đợi

  trace[s]=-2;

  delta[s]= INF;

  while(!q.empty()) {

    int u = q.front(); q.pop();// Lấy đỉnh ở đầu của hàng đợi

    int i = head[u]; // Cung liên thuộc đầu tiên của đỉnh u

    while (i!=0) {  // Còn cung i đi ra từ u

      int v = E[i].y; // v là điểm cuối của cung i

      if(trace[v] == -1){ // Đánh dấu đã thăm đỉnh v

        if (E[i].c-E[i].f> 0) { // Trên cung i còn khả năng tăng luồng

          trace[v] = i;  // Lưu vết: v thuộc cung liên thuộc thứ i

          delta[v]= min(delta[u],E[i].c-E[i].f); // Lương tăng luồng trên cung i

          if(v==t) return delta[t]; // Tới đinht thu, trả về lượng tăng luồng trên cung tới t

          q.push(v); // Còn không thì nạp v vào hàng đợi theo BFS

        }

      }

      i=link[i]; // Cung liên thuộc tiếp theo (nếu i khác 0)

    }

  }

  return 0;

}

int EdmondsKarp() {

  int maxFlow=0;

  while(true) {

    int flow=bfs();// Trả về kết quả tìm đường tăng luồng

    if(flow==0) break; // Nếu kết quả =0: không còn đường tăng luồng thì kết thúc

    maxFlow +=flow; // Cập nhật giá trị luồng cực đại sau một lần tìm đường tăng luồng

    int v = t; // Lần ngược đường tăng luồng để cập nhật luồng trên các cung

    do {

      int i = trace[v]; // Cung i là cung liên thuộc của v

      E[i].f += flow; // Tăng luồng trên cung i (cung thuận)

      E[2*M+1-i].f -= flow; // Giảm luồng trên cung đối của cung i là cung -i

      v= E[i].x; // Lần ngược dần về phía đỉnh phát

    } while( v != s);

  }

  return maxFlow;

}

int main() {

  read_input();

  int FlowValue = EdmondsKarp();

  fo << FlowValue << endl;

  for (int i=1; i<=M; i++)

  if (E[i].f > 0)

fo << E[i].x << ” ” << E[i].y << ” ” << E[i].c << ” ” << E[i].f << endl;

return 0;

}

 b) Thuật toán đẩy tiền luồng giải bài toán luồng cực đại

• Tiền luồng. Cho mạng G(V, E, c, s, t). Một tiền luồng (preflow) là hàm ánh xạ từ tập cung E vào tập số thực

f:  E → ℝ

e→f(e)

thỏa mãn 3 ràng buộc:

+ Với mọi cung e∈E : f(e)≤c(e)

+ Với mọi cung e∈E : f(-e) = f(e) -e là cung đối của e

+ Tổng tiền luồng trên các cung e đi vào đỉnh v (v khác s) là số không âm, ký hiệu là excess[v]≥0. Khi excess[v]>0 thì v gọi là đỉnh tràn (nếu v khác s và t).

• Hàm độ cao h ứng với tiền luồng f trên mạng G(V, E, c, s, t). Đó là ánh xạ từ tập đỉnh V vào tập số tự nhiên

h: V→ℕ

v→h(v)

           thỏa mãn 3 điều kiện (gọi là ràng buộc về độ cao):

+ h(s) = |V|

+ h(t) =0

+ h(u) ≤ h(v) +1 với mọi cung thặng dư (f(e)<c(e)), e=(u,v)

• Khởi trị  trên mạng G = (V, E, s, t, c)

– Khởi trị tiền luồng: f(e)=c(e) với mọi cung đi ra từ s, f(e)=-c(e) nếu có cung –e đi vào s, f(e)=0 trong các trường hợp còn lại,

– Khởi trị hàm độ cao: h(s) = |V |, h(t)=0, còn lại h(v)=1 khi v khác s và t.

– Khởi tạo các giá trị exces[] ứng với tiền luồng f (mức tràn tại các đỉnh)

•  Hàm đẩy luồng pushflow(e):

Trên cung thặng dư e=(u,v) nếu u là đỉnh tràn và u cao hơn v (cụ thể là h(u)=h(v)+1) thì thực hiện đẩy luồng: san bớt một lượng tràn thích hợp của u sang v. Lượng tràn này là ∆=Min{excess(u), cf(u,v)}. Khi đó luồng trên e tăng ∆, trên –e giảm ∆, độ tràn trên u giảm ∆, độ tràn trên v tăng ∆.

• Hàm nâng đỉnh Lift(u):

Với đỉnh u (khác s và t) là đỉnh tràn, nếu không thể chuyển luồng xuống các đỉnh thấp hơn (nghĩa là với mọi cung thặng dư e=(u,v) đều gặp h(u)≤h(v)) thì phải nâng độ cao của đỉnh u bằng độ cao đỉnh v thấp nhất cộng thêm 1.

• Mô hình thuật toán đẩy tiền luồng

Sau khi khởi tại tiền luồng và hàm độ cao, thực hiện hàm Lift(u) hoặc pushflow(e) cho đến khi không thực hiện được hai hàm này. Khi đó tiền luồng f thành luồng cực đại trên mạng

Thời gian trung bình thực hiện thuật toán là O(|E| · |V |2)

Ngày càng có nhiều cải tiến quá trình và thứ tự thực hiện hàm Lift(u) hoặc pushflow(e). Trong đó các thuật toán FIFO Preflow-push với tổ chức dữ liệu dưới dạng danh sách kề hoặc danh sách cung liên thuộc và dùng hàng đợi chứa các đỉnh tràn cùng với sử dụng các mẹo cài đặt (heuristics) khác nhau sẽ cho hiệu quả khác nhau. Nhưng nói chung thời gian thực hiện là O(|V|3 + |V|.|E|).

Với nhận xét: Nếu có số nguyên gap mà 0<gap<|V| mà không có đỉnh nào có độ cao bằng gap (gap gọi là “khe”) thì khi đó mọi đỉnh z có độ cao h(z)>gap sẽ không có đường đi trên các cung thặng dư tới t. Từ đó nảy sinh việc xây dựng hàm đẩy nhãn theo khe: Nếu có gap, mọi đỉnh z khác s có độ cao h[z] mà: gap<h(z)≤|V| sẽ được gán lại nhãn là h(z)=|V|+1. Việc nâng nhãn qua khe vẫn bảo đảm các ràng buộc tiền luồng và ràng buộc độ cao nhưng tạo điều kiện đẩy tiền luồng để cuối cùng không còn đỉnh tràn. Khi đó giá trị tiền luồng chính là giá trị luồng cực đại.

Dưới đây là chương trình thực hiện FIFO Preflow-push với heuristics đẩy nhãn qua khe: Trong thao tác đẩy nhãn qua khe, sử dụng mảng count_[2*M] để đếm số đỉnh có cùng độ cao.

 #include <iostream>

#include <fstream>

#include <queue>

#define maxN 1000

#define maxM 100000

#define maxC 10000

using namespace std;

struct TEdge {long x,y,c,f; } E[2*maxM];

queue<int> Q;

long link[2*maxM];

long head[maxN], current[maxN];

long excess[maxN];

long h[maxN];

long count_[2*maxN];

long N, M, s, t, FlowValue;

ifstream fi (“PreFlowPush.inp”);

ofstream fo (“PreFlowPush.out”);

void read_input() {

     long u, v, c, j;

     fi >> N >> M >> s >> t;

     for (int i=1; i<=M; i++){// Tạo danh sách các cung liên thuộc của mạng và tiền luồng

         fi >> u >> v >> c;

         E[i].x = u;  E[i].y = v; E[i].c = c; // Đưa cung thuận (u,v) vào dslt của u

         link[i] = head[u]; head[u] = i;

         j = 2*M + 1 – i;

         E[j].x = v;  E[j].y = u; E[j].c = 0; // Thêm cung đối (v,u) vào dslt của v

         link[j] = head[v]; head[v] = j;

     }

     // Khởi trị mảng curent[maxN] để biết cung liên kết đi ra khỏi v hiện thời là cung nào

     for (int v=1;v<=N;v++) current[v]=head[v];

}

void Init() { 

     long i, sf, v;

     for (long i=1; i<=2*M; i++) E[i].f=0; // Khởi trị tiền luồng 0

           // Duyệt các cung đi ra khỏi s, đẩy bão hòa các cung đó, cập nhật mức tràn của s

     i= head[s];

     while (i!=0) {

           sf = E[i].c; E[i].f = sf; E[2*M + 1 – i].f = -sf;

           excess[E[i].y] += sf;

           excess[s] -= sf;

           i = link[i];

     }

     // Khởi trị độ cao các đỉnh

     for (int v=1; v<=N; v++) h[v]=1;

     h[s]=N; h[t]=0;

     // Khởi trị mảng đếm số độ cao bằng nhau

     count_[N]=1; count_[0]=1; count_[1]=N-2;

     // Nạp các đỉnh tràn vào hàng đợi Q

     for (int v=1; v<=N; v++)

     if ((v!=s)&&(v!=t)&&(excess[v]>0)) Q.push(v);

}

void Push(long i) { // Hàm đẩy tiền luồng trên cung i

     long delta;

     // Lượng đẩy

     if (excess[E[i].x]<E[i].c-E[i].f) delta=excess[E[i].x];    

         else delta =E[i].c-E[i].f;

     // Thực hiện đẩy luồng trên cung thuận và cung đối, cập nhật mức tràn tại hai đầu cung

     E[i].f += delta;

     E[2*M+1-i].f -=delta;

     excess[E[i].x] -= delta;

     excess[E[i].y] += delta;

}

void SetH(int u, int NewH) {// Cập nhật độ cao mới cho đỉnh u, đồng thời cập nhật count_

     count_[h[u]]–; h[u] = NewH;

     count_[NewH]++;

}

void GapHeuristic(int gap) {// Tìm khe gap và đẩy nhãn h qua khe

     int v;

     if ((0<gap) && (gap<N) && (count_[gap]==0)) // Điều kiện của gap

     for (int v=1; v<=N; v++)

        if ((v!=s) && (gap<h[v]) && (h[v]<=N)) { // Điều kiện đỉnh v được đẩy nhãn

           SetH(v, N+1);    // Thực hiện đẩy nhãn cho v

           current[v] = head[v]; // Lưu cung hiện thời đi ra khỏi v

        }

}

void Lift(int u) { // Hàm nâng nhãn h cho đỉnh u

     long minH, OldH, i;

     minH= 2* maxN;

     i = head[u]; // Duyệt các cung (u,v) thặng dư có h[v] thấp nhất lưu vào minH

     while (i!=0) {

         if  ((E[i].c >E[i].f) && (h[E[i].y]<minH) )

              minH = h[E[i].y];

         i = link[i];

     }

     OldH = h[u]; // Lưu độ cao cũ của u

     SetH(u, minH+1); // Cập nhật độ cao mới cho u, trong đó có giảm count_[OldH]

     GapHeuristic(OldH); // Kiểm tra độ cao cũ có trở thành “gap”, và xử lý

}

void FIFOpreflowpush() { // Thuật toán FIFO đẩy tiền luồng dùng đẩy nhã qua khe

     bool NeedQ; int z; long i;

     while (Q.size()>0) { // Trong khi còn đỉnh tràn, còn thực hiện

        z = Q.front(); Q.pop();// Lấy từ hàng đợi đỉnh tràn z

        while (current[z]!=0) { // Trong khi còn cung hiện thời đi ra từ z

           i= current[z]; // cung i đi ra từ z

           if  ((E[i].c>E[i].f)&&(h[E[i].x]>h[E[i].y])){//có thể đẩy luồng trên i

                                     // Ghi nhận lạ đỉnh cuối cung i có tràn hay không

                NeedQ=((E[i].y!=s)&&(E[i].y!=t)&&(excess[E[i].y]==0));

                // Đẩy luồng theo cung i, làm z bớt tràn dần

                Push(i);

                // Nếu đỉnh cuối cung i là đỉnh không tràn thì sau Push(i) nó thành đỉnh tràn

                if (NeedQ) {

                   Q.push(E[i].y); // Do đó phải nạp nó vào hàng đợi

                   if (excess[z]==0) break; // z hết tràn thì chuyển qua xét điểm khác            

                }

           }

           current[z] = link[i]; // z chưa hết tràn thì xét sang đỉnh khác

        }   

        //  Đã xét hết các đỉnh kề với z mà z vẫn là đỉnh tràn thì phải nâng nhãn cho z

        if (excess[z]>0) {

             Lift(z);  // Nâng nhãn cho z

             current[z]=head[z]; // đặt cung hiện thời đi ra từ z từ đầu dslt

             Q.push(z); // Nạp lại z vào hàng đợi chứa các đỉnh tràn

        }

     }

     // Đã xử lý hết các đỉnh tràn, giá trị tiền luồng là giá trị luồng cực đại

     FlowValue = excess[t];

}          

int main() {

    read_input();

    Init();

    FIFOpreflowpush();

    fo << FlowValue << endl;

    for (long i=1; i<=M ; i++) // Hiện các cung có luồng dương

    if (E[i].f>0)

    fo << E[i].x << ” ” << E[i].y << ” ” << E[i].c << ” ” << E[i].f << endl;

    return 0;

}

 

Chia sẻ:

• X
• Facebook

Thích Đang tải...