From f7d189aa6d545c125b072d65a24844c57150e402 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Mon, 15 Jul 2019 11:17:36 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/graph/flow/max-flow.md | 441 ++++++++++++++++++++------------------------ 1 file changed, 199 insertions(+), 242 deletions(-) diff --git a/docs/graph/flow/max-flow.md b/docs/graph/flow/max-flow.md index 3a8e7646..79adf8c1 100644 --- a/docs/graph/flow/max-flow.md +++ b/docs/graph/flow/max-flow.md @@ -45,70 +45,58 @@ EK 算法的时间复杂度为 $O(n^2m)$ （其中 $n$ 为点数， $m$ 为边 #define INF 0x3f3f3f3f struct Edge { - int from, to, cap, flow; - Edge(int u, int v, int c, int f) - : from(u) - , to(v) - , cap(c) - , flow(f) - { - } + int from, to, cap, flow; + Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {} }; struct EK { - int n, m; - vector edges; - vector G[maxn]; - int a[maxn], p[maxn]; - - void init(int n) - { - for (int i = 0; i < n; i++) - G[i].clear(); - edges.clear(); - } + int n, m; + vector edges; + vector G[maxn]; + int a[maxn], p[maxn]; + + void init(int n) { + for (int i = 0; i < n; i++) G[i].clear(); + edges.clear(); + } - void AddEdge(int from, int to, int cap) - { - edges.push_back(Edge(from, to, cap, 0)); - edges.push_back(Edge(to, from, 0, 0)); - m = edges.size(); - G[from].push_back(m - 2); - G[to].push_back(m - 1); - } + void AddEdge(int from, int to, int cap) { + edges.push_back(Edge(from, to, cap, 0)); + edges.push_back(Edge(to, from, 0, 0)); + m = edges.size(); + G[from].push_back(m - 2); + G[to].push_back(m - 1); + } - int Maxflow(int s, int t) - { - int flow = 0; - for (;;) { - memset(a, 0, sizeof(a)); - queue Q; - Q.push(s); - a[s] = INF; - while (!Q.empty()) { - int x = Q.front(); - Q.pop(); - for (int i = 0; i < G[x].size(); i++) { - Edge& e = edges[G[x][i]]; - if (!a[e.to] && e.cap > e.flow) { - p[e.to] = G[x][i]; - a[e.to] = min(a[x], e.cap - e.flow); - Q.push(e.to); - } - } - if (a[t]) - break; - } - if (!a[t]) - break; - for (int u = t; u != s; u = edges[p[u]].from) { - edges[p[u]].flow += a[t]; - edges[p[u] ^ 1].flow -= a[t]; - } - flow += a[t]; + int Maxflow(int s, int t) { + int flow = 0; + for (;;) { + memset(a, 0, sizeof(a)); + queue Q; + Q.push(s); + a[s] = INF; + while (!Q.empty()) { + int x = Q.front(); + Q.pop(); + for (int i = 0; i < G[x].size(); i++) { + Edge& e = edges[G[x][i]]; + if (!a[e.to] && e.cap > e.flow) { + p[e.to] = G[x][i]; + a[e.to] = min(a[x], e.cap - e.flow); + Q.push(e.to); + } } - return flow; + if (a[t]) break; + } + if (!a[t]) break; + for (int u = t; u != s; u = edges[p[u]].from) { + edges[p[u]].flow += a[t]; + edges[p[u] ^ 1].flow -= a[t]; + } + flow += a[t]; } + return flow; + } }; ``` @@ -139,91 +127,77 @@ Dinic 算法有两个优化： #define INF 0x3f3f3f3f struct Edge { - int from, to, cap, flow; - Edge(int u, int v, int c, int f) - : from(u) - , to(v) - , cap(c) - , flow(f) - { - } + int from, to, cap, flow; + Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {} }; struct Dinic { - int n, m, s, t; - vector edges; - vector G[maxn]; - int d[maxn], cur[maxn]; - bool vis[maxn]; - - void init(int n) - { - for (int i = 0; i < n; i++) - G[i].clear(); - edges.clear(); - } + int n, m, s, t; + vector edges; + vector G[maxn]; + int d[maxn], cur[maxn]; + bool vis[maxn]; + + void init(int n) { + for (int i = 0; i < n; i++) G[i].clear(); + edges.clear(); + } - void AddEdge(int from, int to, int cap) - { - edges.push_back(Edge(from, to, cap, 0)); - edges.push_back(Edge(to, from, 0, 0)); - m = edges.size(); - G[from].push_back(m - 2); - G[to].push_back(m - 1); - } + void AddEdge(int from, int to, int cap) { + edges.push_back(Edge(from, to, cap, 0)); + edges.push_back(Edge(to, from, 0, 0)); + m = edges.size(); + G[from].push_back(m - 2); + G[to].push_back(m - 1); + } - bool BFS() - { - memset(vis, 0, sizeof(vis)); - queue Q; - Q.push(s); - d[s] = 0; - vis[s] = 1; - while (!Q.empty()) { - int x = Q.front(); - Q.pop(); - for (int i = 0; i < G[x].size(); i++) { - Edge& e = edges[G[x][i]]; - if (!vis[e.to] && e.cap > e.flow) { - vis[e.to] = 1; - d[e.to] = d[x] + 1; - Q.push(e.to); - } - } + bool BFS() { + memset(vis, 0, sizeof(vis)); + queue Q; + Q.push(s); + d[s] = 0; + vis[s] = 1; + while (!Q.empty()) { + int x = Q.front(); + Q.pop(); + for (int i = 0; i < G[x].size(); i++) { + Edge& e = edges[G[x][i]]; + if (!vis[e.to] && e.cap > e.flow) { + vis[e.to] = 1; + d[e.to] = d[x] + 1; + Q.push(e.to); } - return vis[t]; + } } + return vis[t]; + } - int DFS(int x, int a) - { - if (x == t || a == 0) - return a; - int flow = 0, f; - for (int& i = cur[x]; i < G[x].size(); i++) { - Edge& e = edges[G[x][i]]; - if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) { - e.flow += f; - edges[G[x][i] ^ 1].flow -= f; - flow += f; - a -= f; - if (a == 0) - break; - } - } - return flow; + int DFS(int x, int a) { + if (x == t || a == 0) return a; + int flow = 0, f; + for (int& i = cur[x]; i < G[x].size(); i++) { + Edge& e = edges[G[x][i]]; + if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) { + e.flow += f; + edges[G[x][i] ^ 1].flow -= f; + flow += f; + a -= f; + if (a == 0) break; + } } + return flow; + } - int Maxflow(int s, int t) - { - this->s = s; - this->t = t; - int flow = 0; - while (BFS()) { - memset(cur, 0, sizeof(cur)); - flow += DFS(s, INF); - } - return flow; + int Maxflow(int s, int t) { + this->s = s; + this->t = t; + int flow = 0; + while (BFS()) { + memset(cur, 0, sizeof(cur)); + flow += DFS(s, INF); } + return flow; + } }; ``` @@ -233,131 +207,114 @@ struct Dinic { ```cpp struct Edge { - int from, to, cap, flow; - Edge(int u, int v, int c, int f) - : from(u) - , to(v) - , cap(c) - , flow(f) - { - } + int from, to, cap, flow; + Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {} }; -bool operator<(const Edge& a, const Edge& b) -{ - return a.from < b.from || (a.from == b.from && a.to < b.to); +bool operator<(const Edge& a, const Edge& b) { + return a.from < b.from || (a.from == b.from && a.to < b.to); } struct ISAP { - int n, m, s, t; - vector edges; - vector G[maxn]; - bool vis[maxn]; - int d[maxn]; - int cur[maxn]; - int p[maxn]; - int num[maxn]; - - void AddEdge(int from, int to, int cap) - { - edges.push_back(Edge(from, to, cap, 0)); - edges.push_back(Edge(to, from, 0, 0)); - m = edges.size(); - G[from].push_back(m - 2); - G[to].push_back(m - 1); - } + int n, m, s, t; + vector edges; + vector G[maxn]; + bool vis[maxn]; + int d[maxn]; + int cur[maxn]; + int p[maxn]; + int num[maxn]; + + void AddEdge(int from, int to, int cap) { + edges.push_back(Edge(from, to, cap, 0)); + edges.push_back(Edge(to, from, 0, 0)); + m = edges.size(); + G[from].push_back(m - 2); + G[to].push_back(m - 1); + } - bool BFS() - { - memset(vis, 0, sizeof(vis)); - queue Q; - Q.push(t); - vis[t] = 1; - d[t] = 0; - while (!Q.empty()) { - int x = Q.front(); - Q.pop(); - for (int i = 0; i < G[x].size(); i++) { - Edge& e = edges[G[x][i] ^ 1]; - if (!vis[e.from] && e.cap > e.flow) { - vis[e.from] = 1; - d[e.from] = d[x] + 1; - Q.push(e.from); - } - } + bool BFS() { + memset(vis, 0, sizeof(vis)); + queue Q; + Q.push(t); + vis[t] = 1; + d[t] = 0; + while (!Q.empty()) { + int x = Q.front(); + Q.pop(); + for (int i = 0; i < G[x].size(); i++) { + Edge& e = edges[G[x][i] ^ 1]; + if (!vis[e.from] && e.cap > e.flow) { + vis[e.from] = 1; + d[e.from] = d[x] + 1; + Q.push(e.from); } - return vis[s]; + } } + return vis[s]; + } - void init(int n) - { - this->n = n; - for (int i = 0; i < n; i++) - G[i].clear(); - edges.clear(); - } + void init(int n) { + this->n = n; + for (int i = 0; i < n; i++) G[i].clear(); + edges.clear(); + } - int Augment() - { - int x = t, a = INF; - while (x != s) { - Edge& e = edges[p[x]]; - a = min(a, e.cap - e.flow); - x = edges[p[x]].from; - } - x = t; - while (x != s) { - edges[p[x]].flow += a; - edges[p[x] ^ 1].flow -= a; - x = edges[p[x]].from; - } - return a; + int Augment() { + int x = t, a = INF; + while (x != s) { + Edge& e = edges[p[x]]; + a = min(a, e.cap - e.flow); + x = edges[p[x]].from; + } + x = t; + while (x != s) { + edges[p[x]].flow += a; + edges[p[x] ^ 1].flow -= a; + x = edges[p[x]].from; } + return a; + } - int Maxflow(int s, int t) - { - this->s = s; - this->t = t; - int flow = 0; - BFS(); - memset(num, 0, sizeof(num)); - for (int i = 0; i < n; i++) - num[d[i]]++; - int x = s; - memset(cur, 0, sizeof(cur)); - while (d[s] < n) { - if (x == t) { - flow += Augment(); - x = s; - } - int ok = 0; - for (int i = cur[x]; i < G[x].size(); i++) { - Edge& e = edges[G[x][i]]; - if (e.cap > e.flow && d[x] == d[e.to] + 1) { - ok = 1; - p[e.to] = G[x][i]; - cur[x] = i; - x = e.to; - break; - } - } - if (!ok) { - int m = n - 1; - for (int i = 0; i < G[x].size(); i++) { - Edge& e = edges[G[x][i]]; - if (e.cap > e.flow) - m = min(m, d[e.to]); - } - if (--num[d[x]] == 0) - break; - num[d[x] = m + 1]++; - cur[x] = 0; - if (x != s) - x = edges[p[x]].from; - } + int Maxflow(int s, int t) { + this->s = s; + this->t = t; + int flow = 0; + BFS(); + memset(num, 0, sizeof(num)); + for (int i = 0; i < n; i++) num[d[i]]++; + int x = s; + memset(cur, 0, sizeof(cur)); + while (d[s] < n) { + if (x == t) { + flow += Augment(); + x = s; + } + int ok = 0; + for (int i = cur[x]; i < G[x].size(); i++) { + Edge& e = edges[G[x][i]]; + if (e.cap > e.flow && d[x] == d[e.to] + 1) { + ok = 1; + p[e.to] = G[x][i]; + cur[x] = i; + x = e.to; + break; + } + } + if (!ok) { + int m = n - 1; + for (int i = 0; i < G[x].size(); i++) { + Edge& e = edges[G[x][i]]; + if (e.cap > e.flow) m = min(m, d[e.to]); } - return flow; + if (--num[d[x]] == 0) break; + num[d[x] = m + 1]++; + cur[x] = 0; + if (x != s) x = edges[p[x]].from; + } } + return flow; + } }; ``` -- 2.11.0