網絡流-Dinic求最大流

2021.8.18

原理：網絡流-EK求最大流

在Dinic求最大流中，d數組變成了步數的記錄，pre數組變成了對其上一條路徑的記錄。

bool bfs() {queue<int>q;memset(d, -1, sizeof d);q.emplace(s), d[s] = 0, pre[s] = head[s];while (!q.empty()) {int t = q.front(); q.pop();for (int i = head[t]; ~i; i = nexte[i]) {int k = to[i];if (d[k] == -1 && wei[i]) {d[k] = d[t] + 1;pre[k] = head[k];if (T == k)return true;q.emplace(k);}}}return false; }

每找到一條可行的路時，會通過find函數找到這條路上的最大可行流，并將其流量去除并建立退流的渠道。

int dinic() {int res = 0, ans;while (bfs()) {while (ans = find_t(s, INF))res += ans;}return res; }

其中的find_t函數為

int find_t(int u, int limit) {if (u == T)return limit;int ans = 0;for (int i = pre[u]; ~i && ans < limit; i = nexte[i]) {pre[u] = i;//優化當前弧int k = to[i];if (d[k] == d[u] + 1 && wei[i]) {int t = find_t(k, min(wei[i], limit - ans));if (!t)d[k] = -1;wei[i] -= t, wei[i ^ 1] += t, ans += t;}}return ans; }

這個函數中，先找到當前點的下一節點，若其是當前節點的下一步，則對其流量進行修改，限制到其本身最大流量與剩余流量，待從源點到匯點所有的可行路都走過之后，返回其能到匯點的最大流量。

多次查詢，保證當前的路徑上所有可行流都能在滿足限制的條件下使用最多。

總結

以上是生活随笔為你收集整理的网络流-Dinic求最大流(仅做自己复习，写的很不清楚)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。