网络流初步

最大流

  • FF算法
  • 每次深搜找一条增广路从S到T,减去当前边的容量,并且建立反悔边,直到原图中没有从S到T的增广路。
  • 代码:
#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算法几乎一样,只是把找增广路变成宽搜就好。
  • 代码:
#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的增广路,删去当前点。
  • 代码:
#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算法求最短路。
  • 代码:
#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:March 14th, 2020 at 09:09 pm