2017年11月30日
最大流的三种算法:Ford-Fulkson、Edmons-Karp、Dinic
这里不介绍算法,只提供模板代码。所有代码基于【P3376】【模板】网络最大流 – 洛谷一题。
Ford-Fulkson
// Code by KSkun, 2017/11
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
struct io {
char buf[1 << 26], *s;
io() {
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0;
while(*s < '0' || *s > '9') s++;
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res;
}
} ip;
#define read ip.read
const int MAXN = 100005;
const int INF = 1e9;
struct Edge {
int to, cap, rev;
Edge(int to, int cap, int rev): to(to), cap(cap), rev(rev) {}
};
std::vector<Edge> vec[MAXN];
bool vis[MAXN];
inline void addedge(int u, int v, int cap) {
vec[u].push_back(Edge(v, cap, vec[v].size()));
vec[v].push_back(Edge(u, 0, vec[u].size() - 1));
}
// Ford-Fulkerson DFS
inline int dfs(int u, int t, int f) {
if(u == t) return f;
vis[u] = true;
for(int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i].to;
if(!vis[v] && vec[u][i].cap > 0) {
int nxt = dfs(v, t, std::min(f, vec[u][i].cap));
if(nxt > 0) {
vec[u][i].cap -= nxt;
vec[v][vec[u][i].rev].cap += nxt;
return nxt;
}
}
}
return 0;
}
inline int max_flow(int s, int t) {
int flow = 0;
for(;;) {
memset(vis, 0, sizeof vis);
int f = dfs(s, t, INF);
if(f == 0) return flow;
flow += f;
}
}
int n, m, s, t, ut, vt, wt;
int main() {
n = read();
m = read();
s = read();
t = read();
for(int i = 0; i < m; i++) {
ut = read();
vt = read();
wt = read();
addedge(ut, vt, wt);
}
printf("%d", max_flow(s, t));
return 0;
}
Edmons-Karp
// Code by KSkun, 2017/11
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
typedef std::pair<int, int> pairi;
struct io {
char buf[1 << 26], *s;
io() {
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0;
while(*s < '0' || *s > '9') s++;
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res;
}
} ip;
#define read ip.read
const int MAXN = 100005;
const int INF = 1e9;
struct Edge {
int to, cap, rev;
Edge(int to, int cap, int rev): to(to), cap(cap), rev(rev) {}
};
std::vector<Edge> vec[MAXN];
std::queue<int> que;
int f[MAXN];
pairi pre[MAXN];
inline void addedge(int u, int v, int cap) {
vec[u].push_back(Edge(v, cap, vec[v].size()));
vec[v].push_back(Edge(u, 0, vec[u].size() - 1));
}
// Edmons-Karp BFS
inline int max_flow(int s, int t) {
int flow = 0;
for(;;) {
memset(f, 0, sizeof f);
while(!que.empty()) que.pop();
que.push(s);
f[s] = INF;
while(!que.empty()) {
int u = que.front();
que.pop();
for(int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i].to;
if(f[v] == 0 && vec[u][i].cap > 0) {
pre[v] = std::make_pair(u, i);
f[v] = std::min(f[u], vec[u][i].cap);
que.push(v);
}
}
if(f[t] != 0) break;
}
if(f[t] == 0) break;
for(int u = t; u != s; u = pre[u].first) {
vec[pre[u].first][pre[u].second].cap -= f[t];
vec[u][vec[pre[u].first][pre[u].second].rev].cap += f[t];
}
flow += f[t];
}
return flow;
}
int n, m, s, t, ut, vt, wt;
int main() {
n = read();
m = read();
s = read();
t = read();
for(int i = 0; i < m; i++) {
ut = read();
vt = read();
wt = read();
addedge(ut, vt, wt);
}
printf("%d", max_flow(s, t));
return 0;
}
Dinic
// Code by KSkun, 2017/11
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
struct io {
char buf[1 << 26], *s;
io() {
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0;
while(*s < '0' || *s > '9') s++;
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res;
}
} ip;
#define read ip.read
const int MAXN = 100005;
const int INF = 1e9;
struct Edge {
int to, cap, rev;
Edge(int to, int cap, int rev): to(to), cap(cap), rev(rev) {}
};
std::vector<Edge> vec[MAXN];
std::queue<int> que;
int level[MAXN];
inline void addedge(int u, int v, int cap) {
vec[u].push_back(Edge(v, cap, vec[v].size()));
vec[v].push_back(Edge(u, 0, vec[u].size() - 1));
}
// Dinic
inline bool bfs(int s, int t) {
memset(level, -1, sizeof level);
level[s] = 0;
que.push(s);
while(!que.empty()) {
int u = que.front();
que.pop();
for(int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i].to;
if(level[v] == -1 && vec[u][i].cap > 0) {
level[v] = level[u] + 1;
que.push(v);
}
}
}
return level[t] != -1;
}
inline int dfs(int u, int t, int left) {
if(u == t || left == 0) return left;
int flow = 0;
for(int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i].to;
if(vec[u][i].cap > 0 && level[v] == level[u] + 1) {
int d = dfs(v, t, std::min(left, vec[u][i].cap));
if(d > 0) {
vec[u][i].cap -= d;
vec[v][vec[u][i].rev].cap += d;
flow += d;
left -= d;
if(left == 0) break;
}
}
}
return flow;
}
inline int max_flow(int s, int t) {
int flow = 0;
while(bfs(s, t)) {
flow += dfs(s, t, INF);
}
return flow;
}
int n, m, s, t, ut, vt, wt;
int main() {
n = read();
m = read();
s = read();
t = read();
for(int i = 0; i < m; i++) {
ut = read();
vt = read();
wt = read();
addedge(ut, vt, wt);
}
printf("%d", max_flow(s, t));
return 0;
}