Một thuật toán mạnh về luồng cực đại

Thảo luận

Mời các bạn tham khảo Thuật toán Dinitz trên Wikipedia

Mã ngồn C++:

#include <algorithm>
#include <vector>
#include <climits>
#include <iostream>
using namespace std;

const int maxnodes = 5000;

int nodes = maxnodes, src, dest;
int dist[maxnodes], q[maxnodes], work[maxnodes];

struct Edge {
  int to, rev;
  int f, cap;
};

vector<Edge> g[maxnodes];

// Adds bidirectional edge
void addEdge(int s, int t, int cap){
  Edge a = {t, g[t].size(), 0, cap};
  Edge b = {s, g[s].size(), 0, cap};
  g[s].push_back(a);
  g[t].push_back(b);
}

bool dinic_bfs() {
  fill(dist, dist + nodes, -1);
  dist[src] = 0;
  int qt = 0;
  q[qt++] = src;
  for (int qh = 0; qh < qt; qh++) {
    int u = q[qh];
    for (int j = 0; j < (int) g[u].size(); j++) {
      Edge &e = g[u][j];
      int v = e.to;
      if (dist[v] < 0 && e.f < e.cap) {
        dist[v] = dist[u] + 1;
        q[qt++] = v;
      }
    }
  }
  return dist[dest] >= 0;
}

int dinic_dfs(int u, int f) {
  if (u == dest)
    return f;
  for (int &i = work[u]; i < (int) g[u].size(); i++) {
    Edge &e = g[u][i];
    if (e.cap <= e.f) continue;
    int v = e.to;
    if (dist[v] == dist[u] + 1) {
      int df = dinic_dfs(v, min(f, e.cap - e.f));
      if (df > 0) {
        e.f += df;
        g[v][e.rev].f -= df;
        return df;
      }
    }
  }
  return 0;
}

int maxFlow(int _src, int _dest) {
  src = _src;
  dest = _dest;
  int result = 0;
  while (dinic_bfs()) {
    fill(work, work + nodes, 0);
    while (int delta = dinic_dfs(src, INT_MAX))
      result += delta;
  }
  return result;
}

int main() {
    int n = 3;
    nodes = n;

    int capacity[][3] = { { 0, 3, 2 }, { 0, 0, 2 }, { 0, 0, 0 } };
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (capacity[i][j] != 0)
                addEdge(i, j, capacity[i][j]);
    cout << (4 == maxFlow(0, 2)) << endl;
}

Nguyễn Hoàng Sơn

2020-10-17 8:35:02

Oh my god :O Em sẽ quay lại học Dinitz T_T

Trùm CUỐI

2020-10-17 8:33:00

Thuật toán FIFOPreFlowPush với Heuristic đẩy nhãn theo khe cài đặt cho bài 556. HMAXFLOW

#include <bits/stdc++.h>
using namespace std;
#define nmax 1001
#define mmax 100001
struct edge {
    int u, v, c, f;
} e[2 * mmax];

int n, m, s, t, head[nmax], link[2 * mmax], cur[nmax];
int h[nmax], cnt[2 * nmax], excess[nmax];
queue<int> q;

void enter() {
    cin >> n >> m >> s >> t;
    for (int i = 1, u, v, c; i <= m; i++) {
        cin >> u >> v >> c;
        e[i] = { u, v, c, 0 };
        e[i + m] = { v, u, 0, 0 };
    }
    memset(head, 0, sizeof head);
    for (int i = 2 * m; i >= 1; i--) {
        link[i] = head[e[i].u];
        head[e[i].u] = i;
    }
    memcpy(cur, head, sizeof head);
}
void init() {
    fill_n(h + 1, n, 1);
    h[s] = n;
    h[t] = 0;
    memset(cnt, 0, sizeof cnt);
    cnt[n] = cnt[0] = 1;
    cnt[1] = n - 2;
    memset(excess, 0, sizeof excess);
    for (int i = head[s]; i; i = link[i]) {
        e[i].f = e[i].c;
        e[i > m ? i - m : i + m].f = -e[i].c;
        excess[e[i].v] += e[i].c;
    }
    for (int u = 1; u <= n; u++)
        if (u != s && u != t && excess[u] > 0)
            q.push(u);
}
void setH(int u, int newH) {
    cnt[h[u]]--;
    h[u] = newH;
    cnt[newH]++;
    cur[u] = head[u];
}
void performGapHeuristic(int gap) {
    if (0 < gap && gap < n && !cnt[gap]) {
        for (int u = 1; u <= n; u++)
            if (gap < h[u] && h[u] <= n)
                setH(u, n + 1);
    }
}
void lift(int u) {
    int gap = h[u], minH = 2 * n;
    for (int i = head[u]; i; i = link[i])
        if (e[i].c > e[i].f && h[e[i].v] < minH)
            minH = h[e[i].v];
    setH(u, minH + 1);
    performGapHeuristic(gap);
}
void push(int i) {
    int u = e[i].u, v = e[i].v, c = e[i].c, f = e[i].f;
    int delta = min(excess[u], c - f);
    excess[u] -= delta;
    excess[v] += delta;
    e[i].f += delta;
    e[i > m ? i - m : i + m].f -= delta;
}

void printResult() {
    cout << excess[t] << '\n';
    for (int i = 1; i <= m; i++)
        if (e[i].f > 0)
            cout << e[i].u << ' ' << e[i].v << ' ' << e[i].f << '\n';
}

void FIFOPreflowPush() {
    init();
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (; cur[u]; cur[u] = link[cur[u]]) {
            int i = cur[u];
            if (e[i].c > e[i].f && h[u] > h[e[i].v]) {
                push(i);
                if (e[i].v != s && e[i].v != t && excess[e[i].v])
                    q.push(e[i].v);
                if (!excess[u])
                    break;
            }
        }
        if (excess[u]) {
            lift(u);
            q.push(u);
        }
    }
    printResult();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    enter();
    FIFOPreflowPush();
}

Mời các bạn tham khảo Thuật toán Dinitz trên Wikipedia

Tổng cộng 2 trả lời

Thuật toán FIFOPreFlowPush với Heuristic đẩy nhãn theo khe cài đặt cho bài 556. HMAXFLOW