Loading... ## 网络流初步 <!--more--> ### 最大流 - FF算法 - 每次深搜找一条增广路从S到T，减去当前边的容量，并且建立反悔边，直到原图中没有从S到T的增广路。 - 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n, m, S, T; struct Edge{ int to, nxt; ll w; }e[200009]; int head[10009], tot = 1; bool vis[10009]; void add(int x, int y, ll w){ e[++tot].to = y; e[tot].w = w; e[tot].nxt = head[x]; head[x] = tot; } ll dfs(int x, ll now){ if(x == T) return now; for(int i = head[x]; i; i = e[i].nxt){ int y = e[i].to; ll w = e[i].w; if(w == 0 || vis[y]) continue; vis[y] = 1; ll res = 0; if((res = dfs(y, min(now, w))) > 0){ e[i].w -= res; e[i^1].w += res; return res; } } return 0; } int main(){ scanf("%d%d%d%d", &n, &m, &S, &T); for(int i = 1; i <= m; i++){ int x, y; ll w; scanf("%d%d%lld", &x, &y, &w); add(x, y, w); add(y, x, 0); } ll ans = 0; while(1){ memset(vis, 0, sizeof(vis)); ll res = dfs(S, 0x3f3f3f3f3f3f3f3f); if(res == 0) break; ans += res; } printf("%lld\n", ans); return 0; } ``` --- - EK算法 - 和FF算法几乎一样，只是把找增广路变成宽搜就好。 - 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n, m, S, T; struct Edge{ int to, nxt; ll w; }e[200009]; int head[10009], tot = 1; int dep[10009]; void add(int x, int y, ll w){ e[++tot].to = y; e[tot].w = w; e[tot].nxt = head[x]; head[x] = tot; } bool bfs(){ memset(dep, 0, sizeof(dep)); queue<int> q; dep[S] = 1; q.push(S); while(!q.empty()){ int x = q.front(); q.pop(); for(int i = head[x]; i; i = e[i].nxt){ int y = e[i].to; ll w = e[i].w; if(w == 0 || dep[y]) continue; dep[y] = dep[x] + 1; q.push(y); } } return dep[T]; } ll dfs(int x, ll now){ if(x == T) return now; ll out = 0; for(int i = head[x]; i; i = e[i].nxt){ int y = e[i].to; ll w = e[i].w; if(w == 0) continue; if(dep[y] != dep[x] + 1) continue; ll res = 0; if((res = dfs(y, min(now, w))) > 0){ e[i].w -= res; e[i^1].w += res; out += res; now -= res; } } if(out == 0) dep[x] = 0; return out; } int main(){ scanf("%d%d%d%d", &n, &m, &S, &T); for(int i = 1; i <= m; i++){ int x, y; ll w; scanf("%d%d%lld", &x, &y, &w); add(x, y, w); add(y, x, 0); } ll ans = 0; while(1){ if(!bfs()) break; ans += dfs(S, 0x3f3f3f3f3f3f3f3f); } printf("%lld\n", ans); return 0; } ``` --- - Dinic算法 - 这个算法效率比较高，主要有下面几个优化： 1. 建立分层图，每一步只能从当前层走向下一层，优化很多。 2. 从当前点开始，计算所能走到T的所有增广路之后再回溯，减少搜索重复部分。 3. 如果当前点没有能到达T的增广路，删去当前点。 - 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n, m, S, T; struct Edge{ int to, nxt; ll w; }e[200009]; int head[10009], tot = 1; int dep[10009]; void add(int x, int y, ll w){ e[++tot].to = y; e[tot].w = w; e[tot].nxt = head[x]; head[x] = tot; } bool bfs(){ memset(dep, 0, sizeof(dep)); queue<int> q; dep[S] = 1; q.push(S); while(!q.empty()){ int x = q.front(); q.pop(); for(int i = head[x]; i; i = e[i].nxt){ int y = e[i].to; ll w = e[i].w; if(w == 0 || dep[y]) continue; dep[y] = dep[x] + 1; q.push(y); } } return dep[T]; } ll dfs(int x, ll now){ if(x == T) return now; ll out = 0; for(int i = head[x]; i; i = e[i].nxt){ int y = e[i].to; ll w = e[i].w; if(w == 0) continue; if(dep[y] != dep[x] + 1) continue; ll res = 0; if((res = dfs(y, min(now, w))) > 0){ e[i].w -= res; e[i^1].w += res; out += res; now -= res; } } if(out == 0) dep[x] = 0; return out; } int main(){ scanf("%d%d%d%d", &n, &m, &S, &T); for(int i = 1; i <= m; i++){ int x, y; ll w; scanf("%d%d%lld", &x, &y, &w); add(x, y, w); add(y, x, 0); } ll ans = 0; while(1){ if(!bfs()) break; ans += dfs(S, 0x3f3f3f3f3f3f3f3f); } printf("%lld\n", ans); return 0; } ``` --- ### 费用流 - 费用流是网络流上加费用的一类问题，每个边有一个费用，流过这条边需要支付流过这条边的流量$\times$当前边的v的费用，我们想要在保证最大流的前提下使费用尽可能多或者少。 - MCMF算法 - 只需要将原来的EK算法的bfs改为SPFA即可， 由于网络流中可能会有负权边，所以不能使用dijkstra算法求最短路。 - 代码： ```cpp #include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int n, m, s, t; struct Edge{ int to, nxt, w, v; }e[400009]; int head[20009], tot = 1; int pre[20009], flw[20009]; bool vis[20009]; int dis[20009]; int maxflow, mincost; void add(int x, int y, int w, int v){ e[++tot].to = y; e[tot].w = w; e[tot].nxt = head[x]; head[x] = tot; e[tot].v = v; } bool bfs(){ memset(vis, 0, sizeof(vis)); memset(dis, 0x3f, sizeof(dis)); memset(flw, 0x3f, sizeof(flw)); queue<int> q; q.push(s); dis[s] = 0; while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0; for(int i = head[x]; i; i = e[i].nxt){ int y = e[i].to, w = e[i].w, v = e[i].v; if(w > 0 && dis[y] > dis[x] + v){ dis[y] = dis[x] + v; flw[y] = min(flw[x], w); pre[y] = i; if(!vis[y]){ vis[y] = 1; q.push(y); } } } } return flw[t] != 0x3f3f3f3f; } void update(){ int x = t; maxflow += flw[t]; mincost += flw[t] * dis[t]; while(x != s){ int i = pre[x]; e[i].w -= flw[t]; e[i^1].w += flw[t]; x = e[i^1].to; } } int main(){ scanf("%d%d%d%d", &n, &m, &s, &t); for(int i = 1; i <= m; i++){ int x, y, w, v; scanf("%d%d%d%d", &x, &y, &w, &v); add(x, y, w, v); add(y, x, 0, -v); } while(bfs()) update(); printf("%d %d\n", maxflow, mincost); return 0; } ``` Last modification：April 6, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏