网络最大流
一、(Edmonds-Karp)算法
不断在残量网络(dfs)进行增广，当不能进行增广时，即为最大流。
code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e4 + 5, M = 2e5 + 5;
int n, m, s, t, pre[M], vis[N];
int cnt = 1, head[N], to[M], nxt[M], val[M];
void add(int u, int v, int w) {
to[++ cnt] = v; val[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt;
}
bool bfs() {
queue <int> q; q.push(s);
memset(vis, 0, sizeof(vis));
memset(pre, 0, sizeof(pre));
vis[s] = 1;
while(! q.empty()) {
int x = q.front(); q.pop();
if(x == t) return true;
for(int i = head[x]; i ; i = nxt[i]) {
if(vis[to[i]] == 1 || val[i] == 0) continue;
pre[to[i]] = i;
q.push(to[i]), vis[to[i]] = 1;
}
}
return false;
}
int EK() {
int ans = 0;
while(bfs()) {
int up = 2e9;
for(int p = t; p != s; p = to[pre[p] ^ 1]) up = min(up, val[pre[p]]);
for(int p = t; p != s; p = to[pre[p] ^ 1]) {
val[pre[p]] -= up;
val[pre[p] ^ 1] += up;
}
ans += up;
}
return ans;
}
int main() {
cin >> n >> m >> s >> t;
for(int i = 1, u, v, w; i <= m; i ++) {
cin >> u >> v >> w;
add(u, v, w); add(v, u, 0);
}
cout << EK() << endl;
return 0;
}
常数巨大，我会告诉你我的(EK)跑了544ms吗？
二、(Dinc)算法
在残量网络上(bfs)构建分层图，再从分层图上(dfs)不断增广。
code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e4 + 5, M = 2e5 + 5, INF = 2e9;
int n, m, s, t, flow, dep[N];
int cnt = 1, head[N], to[M], nxt[M], val[M];
void add(int u, int v, int w) {
to[++ cnt] = v; val[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt;
}
bool bfs() {
memset(dep, 0, sizeof(dep));
queue <int> q; q.push(s);
dep[s] = 1;
while(! q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i ; i = nxt[i]) {
if(dep[to[i]] || val[i] <= 0) continue;
dep[to[i]] = dep[x] + 1;
q.push(to[i]);
}
}
return dep[t] > 0;
}
int dfs(int x, int flow) {
if(x == t) return flow;
int up = 0;
for(int i = head[x]; i ; i = nxt[i]) {
if(val[i] == 0 || dep[to[i]] != dep[x] + 1) continue;
int tmp = dfs(to[i], min(flow, val[i]));
if(tmp == 0) continue;
val[i] -= tmp;
val[i ^ 1] += tmp;
up += tmp; flow -= tmp;
if(flow == 0) return up;
}
return up;
}
int Dinic() {
int ans = 0;
while(bfs()) while(flow = dfs(s, INF)) ans += flow;
return ans;
}
int main() {
cin >> n >> m >> s >> t;
for(int i = 1, u, v, w; i <= m; i ++) {
cin >> u >> v >> w;
add(u, v, w); add(v, u, 0);
}
cout << Dinic() << endl;
return 0;
}
其实我的(Dinic)常数更大，它跑了467ms。
不过，在加入当前弧优化和快读后，它跑了(148ms).(只加当前弧优化时跑(287ms))
当前弧优化：加速跳过枚举不必要的边。
注意在每次(bfs)前对(cur)重新赋值。
核心code:
bool bfs() {
for(int i = 1;i <= n;i ++) cur[i] = head[i];
memset(dep, 0, sizeof(dep));
queue <int> q; q.push(s);
dep[s] = 1;
while(! q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i ; i = nxt[i]) {
if(dep[to[i]] || val[i] <= 0) continue;
dep[to[i]] = dep[x] + 1;
q.push(to[i]);
}
}
return dep[t] > 0;
}
int dfs(int x, int flow) {
if(x == t) return flow;
int up = 0;
for(int &i = cur[x]; i ; i = nxt[i]) {
if(val[i] == 0 || dep[to[i]] != dep[x] + 1) continue;
int tmp = dfs(to[i], min(flow, val[i]));
if(tmp == 0) continue;
val[i] -= tmp;
val[i ^ 1] += tmp;
up += tmp; flow -= tmp;
if(flow == 0) return up;
}
return up;
}
最小费用最大流
最小费用流
将(bfs)改为(spfa)跑最小费用即可。
code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e4 + 5, M = 2e5 + 5;
int n, m, s, t, ans, res, pre[M], vis[N], dis[N];
int cnt = 1, head[N], to[M], nxt[M], val[M], cost[M];
void add(int u, int v, int w, int c) {
to[++ cnt] = v; val[cnt] = w; cost[cnt] = c;
nxt[cnt] = head[u]; head[u] = cnt;
}
bool spfa() {
queue <int> q; q.push(s);
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
vis[s] = 1; dis[s] = 0;
while(! q.empty()) {
int x = q.front(); q.pop();
vis[x] = false;
for(int i = head[x]; i ; i = nxt[i]) {
if(val[i] && dis[to[i]] > dis[x] + cost[i]) {
pre[to[i]] = i;
dis[to[i]] = dis[x] + cost[i];
if(vis[to[i]] == 0) q.push(to[i]), vis[to[i]] = true;
}
}
}
return dis[t] != 0x3f3f3f3f;
}
void EK() {
while(spfa()) {
int up = 2e9;
for(int p = t; p != s; p = to[pre[p] ^ 1]) up = min(up, val[pre[p]]);
for(int p = t; p != s; p = to[pre[p] ^ 1]) {
val[pre[p]] -= up;
val[pre[p] ^ 1] += up;
}
res += up * dis[t];
ans += up;
}
}
int main() {
cin >> n >> m >> s >> t;
for(int i = 1, u, v, w, c; i <= m; i ++) {
cin >> u >> v >> w >> c;
add(u, v, w, c); add(v, u, 0, -c);
}
EK();
cout << ans << " " << res << endl;
return 0;
}