題目描述

給定?nn?個點，mm?條有向邊，給定每條邊的容量，求從點?ss?到點?tt?的最大流。

輸入格式

第一行包含四個正整數nn、mm、ss、tt，用空格分隔，分別表示點的個數、有向邊的個數、源點序號、匯點序號。

接下來mm行每行包含三個正整數u_iui?、v_ivi?、c_ici?，用空格分隔，表示第ii條有向邊從u_iui?出發，到達v_ivi?，容量為c_ici?

輸出格式

一個整數，表示ss到tt的最大流

輸入輸出樣例

輸入 #1?

7 14 1 7 1 2 5 1 3 6 1 4 5 2 3 2 2 5 3 3 2 2 3 4 3 3 5 3 3 6 7 4 6 5 5 6 1 6 5 1 5 7 8 6 7 7

輸出 #1?

14

輸入 #2?

10 16 1 2 1 3 2 1 4 2 5 2 2 6 2 2 3 5 1 3 6 1 4 5 1 4 6 1 1 7 2147483647 9 2 2147483647 7 8 2147483647 10 9 2147483647 8 5 2 8 6 2 3 10 2 4 10 2

輸出 #2?

8 //500ms 秒掉洛谷推流問題 #include <algorithm> #include <iostream> #include <cstring> #include <vector> #include <queue> using namespace std; typedef long long LL; typedef long long F_type; const int MAXN = 1.2e3 + 10, INF = 0x3f3f3f3f; const LL LINF = (LL)INF << 32 | INF; struct Edge {int v, rev;F_type cap;Edge(int a, F_type b, int c) : v(a), rev(c), cap(b) {} }; const F_type maxf=LINF; F_type exflow[MAXN]; int h[MAXN], cnt[MAXN]; int ht, N, S, T, labelcnt; vector<Edge> G[MAXN]; vector<int> hq[MAXN]; void clear(int n = MAXN - 1) {ht = labelcnt = 0;for (int i = 0; i <= n; i++)G[i].clear(); } void addEdge(int u, int v, F_type cap) {G[u].emplace_back(v, cap, G[v].size());G[v].emplace_back(u, 0, G[u].size() - 1); } void update(int u, int newh) {++labelcnt;if (h[u] != N + 1)--cnt[h[u]];h[u] = newh;if (newh == N + 1)return;++cnt[ht = newh];if (exflow[u] > 0)hq[newh].push_back(u); } void globalRelabel() {queue<int> q;for (int i = 0; i <= N + 1; i++)hq[i].clear();for (int i = 0; i <= N; i++)h[i] = N + 1, cnt[i] = 0;q.push(T);labelcnt = ht = h[T] = 0;while (!q.empty()){int u = q.front();q.pop();for (Edge& e : G[u]){if (h[e.v] == N + 1 && G[e.v][e.rev].cap){update(e.v, h[u] + 1);q.push(e.v);}}ht = h[u];} } void push(int u, Edge& e) {if (exflow[e.v] == 0)hq[h[e.v]].push_back(e.v);F_type df = min(exflow[u], e.cap);e.cap -= df;G[e.v][e.rev].cap += df;exflow[u] -= df;exflow[e.v] += df; } void discharge(int u) {int nxth = N + 1;for (Edge& e : G[u])if (e.cap){if (h[u] == h[e.v] + 1){push(u, e);if (exflow[u] <= 0)return;}elsenxth = min(nxth, h[e.v] + 1);}if (cnt[h[u]] > 1)update(u, nxth);elsefor (; ht >= h[u]; hq[ht--].clear()){for (int& j : hq[ht])update(j, N + 1);} } F_type maxFlow(int s, int t, int n) {S = s, T = t, N = n;memset(exflow, 0, sizeof(exflow));exflow[S] = maxf;exflow[T] = -maxf;globalRelabel();for (Edge& e : G[S])push(S, e);for (; ht >= 0; --ht){while (!hq[ht].empty()){int u = hq[ht].back();hq[ht].pop_back();discharge(u);if (labelcnt > (N << 2))globalRelabel();}}return exflow[T] + maxf; }int main() {int n, m, s, t, u, v, w;scanf("%d%d%d%d", &n, &m, &s, &t);while (m--){scanf("%d%d%d", &u, &v, &w);addEdge(u, v, w);}printf("%d", maxFlow(s, t, n));return 0; }

?

總結

以上是生活随笔為你收集整理的图论--网络流--最大流 洛谷P4722（hlpp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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